题解 P1189 【`SEARCH`】

· · 题解

dfs 它不香吗

思路

其实这道题的思路还是比较简单的，就做 N 次 dfs，把每次最后到达的点记录下来就好了。

然而用 dfs 往往就要考虑时间问题，这道题直接搜的时间复杂度是 (R+C)^N，显然会超时。（复杂度我也不确定，反正绝对会超）

所以重点在于如何优化。

记忆化搜索

容易想到用记忆化搜索来优化。

对于每一个操作，如果执行完这个操作到达的点与之前另一个执行完这个操作到达的点相同，那么不管前面的走法有多大不同，现在开始这两个方案就是完全一样的。

由此，我们可以定义一个 bool 数组 vis[dep][x][y] 表示在执行完第 dep 个操作后是否到过点 (x,y)。这就是记忆化搜索。

但可能有人认为（比如我）：这也没有减掉多少种可能啊，怎么就不会超时呢？

但事实上，要执行 N 次，每次少一点，最后会少很多。算一下时间复杂度可能更加明白：每次最多只有 R\times C，总共 N 次，所以复杂度就是 N\times R\times C，显然不超时。

细节

时间满足了，现在再说一下细节部分。

  1. 注意一些读入的细节（例如换行）。

  2. '*'也是能走的。

  3. 记录方向的数组的值和操作数组一定要对应。（不太好描述，可以看后面的代码）

  4. dfs中往后遍历时走不通了直接 break，因为后面也走不了。

代码

你们喜欢的代码在这里~

代码中 n 代表 R；m 代表 C；k 代表 N；深度 dep 是 k最浅，0 最深（这样子好写）。

#include<cstdio>
using namespace std;
const int MAXN=1010;
bool _map[55][55],vis[MAXN][55][55];//是否能走，有没有到过
int to[MAXN],pos[4][2]={1,0,0,1,-1,0,0,-1};//方向数组，操作数组
int read(){//快读
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
void dfs(int dep,int x,int y){//深搜，dep是深度
    if(vis[dep][x][y]) return;//来过就返回
    vis[dep][x][y]=1;//记录
    if(dep==0) return;//这里可以直接返回，因为上一行已经记录了
    while(_map[x+=pos[to[dep]][0]][y+=pos[to[dep]][1]]) dfs(dep-1,x,y);//移动+往下遍历，细节3+细节4，这里压行有点狠
}
int main(){//主函数
    int n=read(),m=read(),sx,sy;//sx和sy是初始位置
    char c,s[10];
    for(int i=1;i<=n;i++){//读入图
        scanf("\n");//细节1
        for(int j=1;j<=m;j++){
            c=getchar();
            if(c=='.') _map[i][j]=1;//记录
            if(c=='*') _map[i][j]=1,sx=i,sy=j;//记录，细节2
        }
    }
    int k=read();
    for(int i=k;i>0;i--){//dep是反的，这里也要反
        scanf("\n%s",s);//细节1
        if(s[0]=='S') to[i]=0;//细节3，想清楚哪边是加哪边是减
        if(s[0]=='E') to[i]=1;
        if(s[0]=='N') to[i]=2;
        if(s[0]=='W') to[i]=3;
    }
    dfs(k,sx,sy);//开始深搜
    for(int i=1;i<=n;i++){//输出
        for(int j=1;j<=m;j++) printf("%c",vis[0][i][j]?'*':(_map[i][j]?'.':'X'));//这里压行也有点狠
        printf("\n");
    }
    return 0;//华丽结束
}

我还是把不压行的代码放一下吧，防止有人不习惯压行……

第一个

while(1){
    x+=pos[to[dep]][0],y+=pos[to[dep]][1];//改变位置
    if(!_map[x][y]) break;//判断退出
    dfs(dep-1,x,y);//往下遍历
}

第二个

if(vis[0][i][j]) printf("*");//最终可以到达
else if(_map[i][j]) printf(".");//可以到达
else printf("X");//不可以到达

看我写了这么多，总得点个赞在走呀~