p1792 走迷宫

题目链接：点击打开链接

//好水的自己，广搜了好多次，都没过，最后只能深搜过了

描述

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

思路：

深搜路线，加判断是否到达

详细看代码

code：

//广搜写了好多遍，一直WA，最后只能深搜了 #include<iostream> using namespace std; int a[101][101];//地图 int fx[4]= {1,-1,0,0}, fy[4]= {0,0,1,-1}; //四个方向 bool temp;//判断是否能走到 int n,x1,x2,y1,y2;//要走的点 void dfs(int x,int y);//深度搜索查找 void print();//输出 int main() { int t; cin>>t; while(t--) { cin>>n; temp=false; string s;//输入一行 for(int i=1; i<=n; ++i) { cin>>s; for(int j=0; j<n; ++j) { if(s[j]=='.') a[i][j+1]=0;//0表示可以走 else a[i][j+1]=1;//1表示不能走 } } cin>>x1>>y1>>x2>>y2; ++x1,++x2,++y1,++y2;//就是不想从一开始 if(a[x1][y1]==1||a[x2][y2]==1) //如果起点或者终点有一个不能通行(为#)，则看成无法办到。 { cout<<"NO"<<endl; continue; } a[x1][y1]=1;//调整开始的值 dfs(x1,y1); print();//输出 } return 0; } void dfs(int x,int y) { if(x==x2&&y==y2)//走到了终点 { temp=1; return ; } int dx,dy; for(int i=0; i<=3; ++i) //四个方向寻找 { dx=x+fx[i]; dy=y+fy[i]; if(dx>0&&dx<=n&&dy>0&&dy<=n&&a[dx][dy]==0)//是否在边界里和是否能走 { a[dx][dy]=1;//调整 dfs(dx,dy);//继续寻找 } } } void print() { if(temp)//表示找到了 cout<<"YES"<<endl; else//没有找到 cout<<"NO"<<endl; }