[题解]洛谷P1189：`SEARCH`

切完这道题我只有一句话想说：DFS要打标……

原题链接：P1189 `SEARCH`

本题既可DFS又可BFS，输入输出也颇具可视化风格（但样例敲的真心累死），不过首次提交却只有30分，好端端一dfs你给我跑T……那么我也没话可说。

暴搜路径这种操作没什么需要注意的。但是打标记就很重要了。经过思考我们可以发现搜索中存在很大重复的部分，在同一深度可能会对一个相同的点进行很多次搜索，极大地浪费了时间，于是维护一个标记数组f[depth][x][y]表示在递归深度为depth时已经搜索过(x,y)这个点，并在递归开始时判断标记，为真则直接返回不进行搜索（显然你需要的可能的解已经搜过了）。

本题合计提交次数：⑨

第1次   0分 RE  i--写成i++，stack存爆
第2次  30分 TLE 没有维护标记导致重复计算
第3次   0分 WA  试图用clock()卡时间，但阈值设置过小，实际上是单位搞错
第4次  20分 WA  同上
第5次  40分 WA  clock()起作用，分数提高10分
第6次   0分 CE  时间单位换算时使用了未定义的常量
第7次  40分 WA  时间单位换算正确，但中止搜索多半会漏解，40分是极限
第8次  20分 WA  标记维护失误，对每个点保存搜索过的方向会影响搜索的进行，导致漏解
第9次 100分 AC

R17635685

#include<bits/stdc++.h>
using namespace std;
const int MAXR = 53;
const int MAXN = 1007;
int R,C;
char a[MAXR][MAXR];
bool f[MAXN][MAXR][MAXR];
char mstk[MAXN];
stack<char> opt;
void dfs(int x,int y,int depth){
    if(opt.empty()){
        a[x][y]='*';
        return;
    }
    if(f[depth][x][y])return;
    f[depth][x][y]=1;
    char tgt=opt.top();
    opt.pop();
    if(tgt=='S'){
        for(int i=x+1;i<R;i++){
            if(a[i][y]=='X')break;
            dfs(i,y,depth+1);
        }
    }else if(tgt=='N'){
        for(int i=x-1;i>=0;i--){
            if(a[i][y]=='X')break;
            dfs(i,y,depth+1);
        }
    }else if(tgt=='W'){
        for(int i=y-1;i>=0;i--){
            if(a[x][i]=='X')break;
            dfs(x,i,depth+1);
        }
    }else if(tgt=='E'){
        for(int i=y+1;i<C;i++){
            if(a[x][i]=='X')break;
            dfs(x,i,depth+1);
        }
    }
    opt.push(tgt);
}
int main(){
    memset(a,0,sizeof(a));
    memset(f,0,sizeof(f));
    memset(mstk,0,sizeof(mstk));
    scanf("%d%d",&R,&C);
    int sx,sy;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            a[i][j]=getchar();
            while(a[i][j]=='\r'||a[i][j]=='\n')a[i][j]=getchar();
            if(a[i][j]=='*'){
                sx=i;
                sy=j;
                a[i][j]='.';
            }
        }
    }
    int N;
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        char s[6];
        scanf("%s",s);
        //opt.push(s[0]);
        mstk[i]=s[0];
    }
    for(int i=N-1;i>=0;i--)opt.push(mstk[i]);
    dfs(sx,sy,0);
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++)putchar(a[i][j]);
        putchar('\n');
    }
    return 0;
}

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

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

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