洛谷 p1605 迷宫问题 详解
心不懈 人气:0
题解:dfs搜索
#include <iostream> #include <algorithm> #include <cstring> #include <stdio.h> using namespace std; int map[6][6];//地图 bool temp[6][6];//走过的标记 int dx[4]={0,0,1,-1};//打表 int dy[4]={-1,1,0,0}; int sx,sy,fx,fy,total,l,r,n,m; void walk(int x,int y)//x和y分别表示走到的点 { if(x==fx&&y==fy)//如果刚好达到终点,则方案加1 { total++; return ; } else { for(int i=0;i<=3;i++)//i《=3意思就是四个方向进行遍历 { int a=x+dx[i];//下一个位置 int b=y+dy[i]; if(temp[a][b]==0&&map[a][b]==1)//判断没有走过,并且没有障碍 { temp[x][y]=1;//标记 walk(a,b);//继续搜下一个点 temp[x][y]=0;//恢复 } } } } int main () { int n,m,t; cin>>n>>m>>t; for(int ix=1;ix<=n;ix++)//把所给的区域变成1 { for(int iy=1;iy<=m;iy++) { map[ix][iy]=1; } } cin>>sx>>sy>>fx>>fy; int l,r; for(int u=0;u<t;u++) { cin>>l>>r; map[l][r]=0;//障碍标记成0 } walk(sx,sy);//搜索一般都是起点坐标 cout<<total; return 0; }
加载全部内容