题解 P1605 【迷宫】

在下刚刚学完深搜，就做了一题AC，~~都不好意思说~~~~自己是蒟蒻了~~（好吧，我本就是蒟蒻） 反正，这题除了深搜，还是深搜。 深搜，一句话来总结一下，就是： # 不撞南墙不回头 而在这题里，“南墙”有三个： ### 第一个是真墙：迷宫的围墙 也就是俗话所说的越界。越界了你还不回头，你是想去哪儿？ ### 第二个是山墙:障碍物T（姑且认为是山） 如果一座山横在你面前，你还是绕路吧！ ### 第三个是人造墙：题目说了每个方格最多只能走一次 这是真没办法 所以深搜的返回条件就出来了——就是以上那三堵墙 我们每次可以从上下左右四个方向进行深搜，一旦遇上南墙就返回，如果走到了重点，s++。 #### 记住了，题目里说保证起点没有障碍，并没有保证重点也没有啊 好了，上代码吧 ```cpp #include<bits/stdc++.h> using namespace std; int a[6][6]; int tx,ty,sx,sy,fx,fy,t; int n,m,s; void dfs(int x,int y)//用x来表示x坐标，y来表示y坐标 { if(x<1||x>n)//x坐标越界 return; if(y<1||y>m)//y坐标越界 return; if(x==fx&&y==fy) { s++;//终点站到了 return; } if(a[x][y]==1||a[x][y]==2)//1代表走过了，2代表障碍 return; a[x][y]=1; dfs(x+1,y);//下 dfs(x,y+1);//右 dfs(x-1,y);//上 dfs(x,y-1);//左 a[x][y]=0;//清零 } int main() { cin>>n>>m>>t; cin>>sx>>sy>>fx>>fy; for(int i=0;i<t;i++) { cin>>tx>>ty; a[tx][ty]=2;//标记障碍 } if(a[fx][fy]==2)//如果终点有障碍 { cout<<"0";//就没必要搜了 return 0;//肯定搜不到 } dfs(sx,sy);//从起点开始 cout<<s; return 0; } ``` 嗯，我看到标签里有枚举和暴力，这题能用枚举？~~（怀疑智商）~~ 还有递推，有谁找到这题的递推关系式了？请评论区留个言，谢谢