P1605 迷宫——题解

解题思路

使用 DFS 枚举路径。进入格子时标记为已访问，尝试四个方向；递归返回后取消标记，使该格子可以在其他路径中使用。到达终点时找到一条完整路径并累加答案。

复杂度分析

迷宫最多 $25$ 格，复杂度与合法简单路径数量有关，最坏可写为 $O(4^{NM})$；空间复杂度 $O(NM)$。

易错点

起点要预先标记；障碍和已访问格都不能进入；回溯时必须撤销访问标记。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int n,m,t,sx,sy,fx,fy,ans; bool ban[6][6],vis[6][6];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
void dfs(int x,int y){
    if(x==fx&&y==fy){ans++;return;}
    for(int k=0;k<4;k++){
        int nx=x+dx[k],ny=y+dy[k];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!ban[nx][ny]&&!vis[nx][ny]){
            vis[nx][ny]=true; dfs(nx,ny); vis[nx][ny]=false;
        }
    }
}
int main(){
    cin>>n>>m>>t>>sx>>sy>>fx>>fy;
    while(t--){int x,y;cin>>x>>y;ban[x][y]=true;}
    vis[sx][sy]=true; dfs(sx,sy);
    cout<<ans<<'\n'; return 0;
}

#include <bits/stdc++.h> using namespace std; int n,m,t,sx,sy,fx,fy,ans; bool ban[6][6],vis[6][6]; int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; void dfs(int x,int y){ if(xfx&&yfy){ans++;return;} for(int k=0;k<4;k++){ int nx=x+dx[k],ny=y+dy[k]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!ban[nx][ny]&&!vis[nx][ny]){ vis[nx][ny]=true; dfs(nx,ny); vis[nx][ny]=false; } } } int main(){ cin>>n>>m>>t>>sx>>sy>>fx>>fy; while(t--){int x,y;cin>>x>>y;ban[x][y]=true;} vis[sx][sy]=true; dfs(sx,sy); cout<<ans<<'\n'; return 0; }