[SOJ] 无路可逃？

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

Sample Output

0

1

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

#include<iostream>

#include<queue>

#include<memory>

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<point>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<<endl;

    else cout<<0<<endl;

  }

  return 0;

}

秒客网

[SOJ] 无路可逃？

相关文章