题目描述

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

思路

暴力广搜，判重就可以了
O(n^2)

#include 
#include 
#include 
using namespace std;
int m,start[3],end[3],a[20][20],fl=0;
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int bfs()
{
    queue tx; queue ty;
    tx.push(start[1]); ty.push(start[2]);
    while (!tx.empty())
    {
        int xx=tx.front(),yy=ty.front();
        tx.pop(); ty.pop();
        if (xx==end[1]&&yy==end[2]) 
        {
            printf("YES\n");
            fl=1;   
            return 0;
        }
        for (int i=1;i<=4;i++)
            if (dx[i]+xx>=1&&dx[i]+xx<=m&&dy[i]+yy>=1&&dy[i]+yy<=m&&a[dx[i]+xx][dy[i]+yy]==0)
            {
                a[dx[i]+xx][dy[i]+yy]=1;
                tx.push(dx[i]+xx);
                ty.push(dy[i]+yy);

            }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for (int k=1;k<=n;k++)
    {
        fl=0;
        scanf("%d",&m);
        for (int i=1;i<=m;i++)
        {
            char ch[20];
            scanf("%s",&ch);
            for (int j=1;j<=m;j++)
            {
                if (ch[j-1]=='#') a[i][j]=1;
                if (ch[j-1] == 's') 
                {
                    start[1]=i;
                    start[2]=j;
                }
                if (ch[j-1] == 'e') 
                {
                    end[1]=i;
                    end[2]=j;
                }
            }
        }
        bfs();
        if (fl==0) printf("NO\n");
    }
}