题解：P15682 [ICPC 2023 Jakarta R] Easy As ABC

· · 题解

前置知识

深搜。

思路

枚举出发点搜索后两位，状态 vis_{i,j} 记录点 (i,j) 是否被访问过，枚举完第三位是更新答案回溯。时间复杂度 O(n^6)

代码

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e4+4;
char a[4][4];
int d[10][2]={{0,1},{1,1},{1,0},{-1,1},{-1,-1},{1,-1},{0,-1},{-1,0}};
int vis[4][4];
string ans="ZZZ",s="   ";
void dfs(int x,int y,int t){
    if(t==3){
        ans=min(ans,s);
        return;
    }
    vis[x][y]=1;
    s[t]=a[x][y];
    for(int i=0;i<8;i++){
        int xx=x+d[i][0],yy=y+d[i][1];
        if(xx<4&&xx>0&&yy<4&&yy>0&&vis[xx][yy]==0){
            dfs(xx,yy,t+1);
        }
    }
    vis[x][y]=0;
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            dfs(i,j,0);
        }
    }
    cout<<ans;
    return 0;
}

实现细节