题解 P1605 【迷宫】

Billy●Herrington

2018-08-06 14:18:52

Solution

大扎好,我系世界第一蒟蒻czdh。介系我发布的第2篇题解 首先,这一题一看就知道一定要用**dfs回溯**。因为我们要枚举走的步数,以及走错路时抑制住自己的愤怒回来换下一条路。 看到有不少人在讨论版里发只有**40**分(~~我一开始也只有40分~~。),关于这个问题,我会在代码里解释。 ## 以下是代码: ```cpp #include <iostream> #include <cstdio> using namespace std; bool G[15][15],VIS[15][15];//G为总地图,VIS记录是否访问 int n,m,d[5]={-1,0,1,0,-1};//方向不解释 int nx,ny,ex,ey,CNT; //nx,ny起点坐标;ex,ey终点坐标,CNT路径条数 void dfs(int x,int y) { if (x ==ex&&y ==ey)//如果到终点 { CNT++;//路径加一 return;//回去继续查找 } for (int k=0;k<4;k++) { int l=x+d[k];int r=y+d[k+1]; if (l>=1&&r>=1&&l<=n&&r<=m&&!G [l][r]&&!VIS [l][r]) { VIS [l][r]=true;//标记为已访问 dfs (l,r); VIS [l][r]=false;//回溯 } } return; } int main () { int t,zx,zy; cin>>n>>m>>t>>nx>>ny>>ex>>ey; G[nx][ny]=true; //这就是许多人(我)40分的原因 //因为dfs函数里并没有将起点设为已访问 //所以在后面的访问里,可能访问起点许多次 //所以你的答案可能比标准答案多 while(t--) { cin>>zx>>zy; G[zx][zy]=true;//设为障碍 } dfs (nx,ny);//从起点开始寻找 cout<<CNT; return 0; } ``` 蒟蒻第二次发布题解,请大家指教qwq 蟹蟹大家qwq