[题解]洛谷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]

最后修改:2019 年 03 月 15 日 03 : 52 PM
欢迎投食喵 ~

发表评论