P7555 [USACO21OPEN] Maze Tac Toe S 题解

· · 题解

建议读懂题目后再阅读下面的内容。

首先我们发现，可以使用一个 3^9 大小的数字储存下一个井字棋状态。由于 3^9 \leq 2*10^5，所以我们可以考虑 O(3^9N^2) 的方法。

考虑进行深度优先搜索。使用 bool hav[N][N][3**9] 记录下这个状态是否出现过（位置和井字棋的状态），防止重复搜索。如果没有被搜索过，首先判断这个位置上要不要填入棋子，需要的话改变状态。然后判断这个状态是否胜利，是的话记录并且退出。最后想四个方向进行搜索即可。

对于可行状态，可以直接转换成 3*3 的数组，然后暴力判断。建议先预处理出所有状态的可行性。

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;
int N;
char Maz[30][100];
int pw[10];
int fang[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool dp[30][30][20010];
bool pd[20010];
bool isP[20010];
char mp[5][5];
inline bool isWin(int k){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++){
            mp[i][j]=k%3;
            if(mp[i][j]==0) mp[i][j]='.';
            else if(mp[i][j]==1)    mp[i][j]='M';
            else    mp[i][j]='O';
            k/=3;
        }
    string p="";
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            p+=mp[i][j];
        if(p=="MOO" || p=="OOM")    return true;
        p="";
    }
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++)
            p+=mp[j][i];
        if(p=="MOO" || p=="OOM")    return true;
        p="";
    }
    for(int i=1;i<=3;i++)
        p+=mp[i][i];
    if(p=="MOO" || p=="OOM")    return true;
    p="";
    for(int i=1;i<=3;i++)
        p+=mp[i][4-i];
    if(p=="MOO" || p=="OOM")    return true;
    return false;
}
int Draw(int k,char q,int x,int y){
    x=3*x+y;
    int u=(k/pw[x])%3;
    if(u!=0)    return k;
    return k+(q=='M'?1:2)*pw[x];
}
int ans;
void dfs(int x,int y,int k){
    if(Maz[x][3*y+1]=='M' || Maz[x][3*y+1]=='O')
        k=Draw(k,Maz[x][3*y+1],Maz[x][3*y+2]-'1',Maz[x][3*y+3]-'1');
    if(dp[x][y][k]) return;
    dp[x][y][k]=true;
    if(isP[k]){
        ans+=!pd[k];
        pd[k]=true;
        return;
    }
    for(int i=0,xx,yy;i<4;i++){
        xx=x+fang[i][0],yy=y+fang[i][1];
        if(Maz[xx][3*yy+1]!='\0' && Maz[xx][3*yy+1]!='#')
            dfs(xx,yy,k);
    }
}
int main(){
    pw[0]=1;
    for(int i=1;i<=9;i++)   pw[i]=pw[i-1]*3;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf(" %s",Maz[i]+1);
    for(int i=0;i<pw[9];i++)    isP[i]=isWin(i);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(Maz[i][3*j+1]=='B')
                dfs(i,j,0);
    printf("%d",ans);
    return 0;
}