Description

唐僧被妖怪关在迷宫中。孙悟空好不容易找到一张迷宫地图，并通过一个魔法门来到来到迷宫某个位置。假设迷宫是一个n*m的矩阵，它有两种地形，1表示平地，0表示沼泽，孙悟空只能停留在平地上。孙悟空目前的位置在坐标(sx,sy)处，他可以向上下左右四个方向移动。

请你帮助孙悟空计算一下，迷宫中是否存在一条路从他所在位置(sx,sy)到达唐僧所在位置(tx,ty)？

 

Input

输入第一行为一个整数t（0<t<=10），表示测试用例个数。

每个测试样例的第1行是2个正整数n (1≤n≤100)，m (1≤n≤100)，表示迷宫是n*m的矩阵。接下来的n行输入迷宫，每行有m个数字（0或者1），数字之间用一个空格间隔。

接下来的1行是4个整数sx,sy,tx,ty，1≤sx,tx≤n，1≤sy,ty≤m，表示孙悟空所在位置为第sx行第sy列，唐僧所在位置为第tx行第tx列。迷宫左上角编号是(1,1)，右下角编号是(n, m)。

数据保证(sx,sy)格和(tx,ty)必定为平地。

 

Output

每个样例单独输出一行：1表示路径存在，0表示路径不存在。

 

Sample Input

 Copy sample input to clipboard

22 21 00 11 1 2 24 4 1 1 1 01 0 1 11 0 1 11 1 1 01 1 3 4

Sample Output

01 解题思路： 把矩阵遍历一遍，如果终点被遍历，则存在一条路

#include
      
       #include
       
        #include
        
         using namespace std;struct point{  int x;  int y;    point(int sx, int sy)  {    this->x=sx;    this->y=sy;  }  point(){}};const int MAX = 105;int n, m;int edge[MAX][MAX];bool isvisited[MAX][MAX];queue
         
          q;int dx[4]={0, 0, -1, 1};int dy[4]={1, -1, 0, 0};void BFS(int sx, int sy){  point temp, temp1;  q.push(point(sx, sy));  isvisited[sx][sy]=true;  while(!q.empty())  {    temp=q.front();    q.pop();    for(int i=0;i<4;i++)    {      temp1.x=temp.x+dx[i];      temp1.y=temp.y+dy[i];      if(temp1.x>=1&&temp1.y>=1&&!isvisited[temp1.x][temp1.y]&&edge[temp1.x][temp1.y])      {        isvisited[temp1.x][temp1.y]=true;        q.push(temp1);      }    }  }}int main(){  int t;  cin>>t;  while(t-->0)  {    cin>>n>>m;        memset(edge, 0, sizeof(edge));    memset(isvisited, false, sizeof(isvisited));    for(int i=1;i<=n;i++)      for(int j=1;j<=m;j++)      {        cin>>edge[i][j];      }        int sx, sy;    int tx, ty;    cin>>sx>>sy>>tx>>ty;    BFS(sx, sy);        if(isvisited[tx][ty])      cout<<1<