题解 P1605 【迷宫】
Billy●Herrington
2018-08-06 14:18:52
大扎好,我系世界第一蒟蒻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