#include
using namespace std;
char maze[101][101][101] = {0}; //存放输入的符号
int maze_mark[101][101] = {0}; //判断每个位置是否被走过,0表示没走过,1表示走过
int n; //规模大小
int one_x[101], one_y[101], two_x[101], two_y[101]; //(one_x, one_y)起始点,(two_x, two_y)终点
void my_function(int begin_x, int begin_y, int num)
{
if (begin_x < 0 || begin_x >= n)
return;
if (1 == maze_mark[begin_x][begin_y] || '#' == maze[begin_x][begin_y][num])
return;
else
{
maze_mark[begin_x][begin_y] = 1;
if ((begin_x - 1 >= 0) && (maze[begin_x - 1][begin_y][num] == '.') &&
(!maze_mark[begin_x - 1][begin_y]))
my_function(begin_x - 1, begin_y, num);
if ((begin_x + 1 < n) && (maze[begin_x + 1][begin_y][num] == '.') &&
(!maze_mark[begin_x + 1][begin_y]))
my_function(begin_x + 1, begin_y, num);
if ((begin_y - 1 >= 0) && (maze[begin_x][begin_y - 1][num] == '.') &&
(!maze_mark[begin_x][begin_y - 1]))
my_function(begin_x, begin_y - 1, num);
if ((begin_y + 1 < n) && (maze[begin_x][begin_y + 1][num] == '.') &&
(!maze_mark[begin_x][begin_y + 1]))
my_function(begin_x, begin_y + 1, num);
}
}
int main()
{
int cycle;
cin >> cycle;
while (cycle--)
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> maze[i][j][cycle];
cin >> one_x[cycle], one_y[cycle], two_x[cycle], two_y[cycle];
}
while (cycle--)
{
memset(maze_mark, 0, sizeof(maze_mark));
if ((one_x[cycle] == two_x[cycle]) && (one_y[cycle] == two_y[cycle])) //起始点就等于终点
{
cout << "YES" << endl;
continue;
}
if (two_x[cycle]< 0 || two_x[cycle] >= n || two_y[cycle] < 0 || two_y[cycle] >= n)
continue;
my_function(one_x[cycle], one_y[cycle], cycle);
if (maze_mark[two_x[cycle]][two_y[cycle]])
printf("YES\n");
else
printf("NO\n");
}
getchar();
return 0;
}
题目描述
一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态, . 和#, 前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点 上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。
输入格式
第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为 . 或者 #。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出格式
k行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。
样例输入
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
样例输出
YES
NO