首页 > 代码库 > NOI openjudge 1792.迷宫

NOI openjudge 1792.迷宫

2024-09-10 10:27:28   208人阅读

一天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”。

样例输入

23.##..##..0 0 2 25.....###.#..#..###.....#.0 0 4 0

样例输出

YESNO
这是一个迷宫类问题；从一个点到达另一个点，路上有障碍不能通行；只能走上下左右四个方向；而不能走斜向；下面是代码；
#include<iostream>using namespace std;int mg[105][105],jg=0,zs,a,b,n,ax,ay,bx,by;bool bl[105][105]={0};int ab(int);void fin(int x,int y){    if(x==bx&&y==by)        {            jg=1;            return;        }    if(bl[x][y]||!(mg[x][y]))return;    else     {        bl[x][y]=1;        fin(x-1,y);        fin(x+1,y);        fin(x,y-1);        fin(x,y+1);    }}int main(){    cin>>zs;    while(zs--)    {        jg=0;        char sum;        cin>>n;        for(int i=0;i<n;++i)            for(int j=0;j<n;++j)                {                    cin>>sum;                    if(sum==‘.‘)                        {                            mg[i][j]=1;                            bl[i][j]=false;                        }                    else                     {                        bl[i][j]=true;//记录走过的路和不能走的路；                         mg[i][j]=0;                    }                }        cin>>ax>>ay>>bx>>by;        if(mg[ax][ay]!=1||mg[bx][by]!=1)            {                cout<<"NO"<<endl;//剪枝
                continue;            }            fin(ax,ay);        if(jg)                cout<<"YES"<<endl;            else cout<<"NO"<<endl;     }    return 0;}int ab(int a){    if(a<0)return -a;    else return a;}
 
NOI openjudge 1792.迷宫






























        

            
                
                  
                
                

                    联系

                    我们