codevs 1215 迷宫

题目描述 Description

在N*N的迷宫内，“#”为墙，“.”为路，“s”为起点，“e”为终点，一共4个方向可以走。从左上角（(0,0)“s”）位置处走到右下角（(n-1,n-1)“e”）位置处，可以走通则输出YES，不可以走则输出NO。

输入描述 Input Description

输入的第一行为一个整数m，表示迷宫的数量。
其后每个迷宫数据的第一行为一个整数n（n≤16），表示迷宫的边长，接下来的n行每行n个字符，字符之间没有空格分隔。

输出描述 Output Description

输出有m行，每行对应的迷宫能走，则输出YES，否则输出NO。

样例输入 Sample Input

1
7
s…##.
.#…..
…….
..#….
..#…#
###…#
……e

样例输出 Sample Output

YES

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct qer
{
	int x, y;
};
queue <qer> q;
char maps[105][105];
bool v[105][105];
int fx[5] = {0, 1, -1, 0, 0};
int fy[5] = {0, 0, 0, 1, -1};
void bfs(int x1, int y1, int x2, int y2, int n)
{
    q.push((qer){x1,y1});
    v[x1][y1] = 1;
    while(q.size())
    {
        qer now = q.front();
        q.pop();
        if(now.x == x2 && now.y == y2)
		{
            cout << "YES" << endl;
            return;
        }
        for(int i = 1; i <= 4; i ++)
        {
            int x = now.x + fx[i];
            int y = now.y + fy[i];
            if(x > 0 && x <= n && y > 0 && y <= n && maps[x][y] != '#' && !v[x][y])
            {
                q.push((qer){x,y});
                v[x][y] = 1;
            }
        }
    }
    cout << "NO" << endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n, x1, y1, x2, y2;
		scanf("%d", &n);
		for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
		{
            cin >> maps[i][j];
            if(maps[i][j] == 's')
				x1 = i, y1 = j;
            else if(maps[i][j] == 'e')
				x2 = i, y2 = j;
        }
		bfs(x1, y1, x2, y2, n);
	}
	return 0;
}