[题解]洛谷P1605：迷宫

起因是最近教练讲了DFS，找水题做的时候发现这题我只有40分？！于是就随手把它清算了。

原题链接：P1605 迷宫

大概是珂以DP的，但是数据范围小的一批用DFS也能3ms搜过去。
开一个N*M大小的布尔型标记数组维护能不能走，设计函数dfs(nx,ny)搜索从坐标(nx,ny)到(FX,FY)的路径；显然，对一个点至多有四种走法（上下左右），但需要事先判断合不合法（直接看标记），于是就宏定义一个“DFS if possible”：

#define dip(x,y) if(!a[(x)][(y)])dfs((x),(y));

其中a是标记数组，true表示不能走。对a的维护可以分为两部分进行，第一部分是预处理，在地图的边界上全部标true防止走超，并对每个障碍物打标；第二部分在dfs过程中将访问过的点标记（当然结束之前要复原）。

傻逼题，随手即可AC -> R17232741

#include<bits/stdc++.h>
#define dip(x,y) if(!a[(x)][(y)])dfs((x),(y));
using namespace std;
bool a[7][7];
int ans=0;
int N,M,T;
int FX,FY;
void dfs(int nx,int ny){
    if(nx==FX&&ny==FY){
        ans++;
        return;
    }
    a[nx][ny]=1;
    dip(nx+1,ny);
    dip(nx-1,ny);
    dip(nx,ny+1);
    dip(nx,ny-1);
    a[nx][ny]=0;
}
int main(){
    scanf("%d%d%d",&N,&M,&T);
    int SX,SY;
    scanf("%d%d%d%d",&SX,&SY,&FX,&FY);
    memset(a,0,sizeof(a));
    for(int i=0;i<7;i++)a[0][i]=a[i][0]=1;
    for(int i=0;i<7;i++)a[N+1][i]=1;
    for(int i=0;i<7;i++)a[i][M+1]=1;
    while(T--){
        int tx,ty;
        scanf("%d%d",&tx,&ty);
        a[tx][ty]=1;
    }
    dfs(SX,SY);
    printf("%d",ans);
    return 0;
}

最后，我是氼，我淼题。
[heimu]我是水人，我水，水/水题[/heimu]

版权声明：本文是原创文章，版权归 无限UCW 所有。

本文链接：https://ucw.moe/archives/solution-luogu-p1605.html

本站所有原创文章采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。
您可以自由地转载和修改，但请务必注明文章来源并且不可用于商业目的。