zoj1103.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
using namespace std;

struct Node{
    int p1, p2, p3, st;
    Node(int a = 0, int b = 0, int c = 0, int d = 0) : p1(a), p2(b), p3(c), st(d) {}
} q[625010];
int n;
char c[51][51];
bool f[51][51][51];


void solve(){
    memset(f, 0, sizeof(f));
    f[q[0].p1][q[0].p2][q[0].p3] = 1; q[0].st = 0;
    if (q[0].p1 == q[0].p2 && q[0].p1 == q[0].p3){
        puts("0"); return;
    }
    int s = 0, t = 0;
    while (s <= t){
        for (int i = 1; i <= n; i++)
            if (!f[i][q[s].p2][q[s].p3] && c[q[s].p1][i] == c[q[s].p2][q[s].p3]){
                q[++t] = Node(i, q[s].p2, q[s].p3, q[s].st + 1);
                f[i][q[s].p2][q[s].p3] = 1;
                if (q[t].p1 == q[t].p2 && q[t].p1 == q[t].p3){
                    printf("%d\n", q[t].st); return;
                }   
            }
        
        for (int i = 1; i <= n; i++)
            if (!f[q[s].p1][i][q[s].p3] && c[q[s].p2][i] == c[q[s].p1][q[s].p3]){
                q[++t] = Node(q[s].p1, i, q[s].p3, q[s].st + 1);
                f[q[s].p1][i][q[s].p3] = 1;
                if (q[t].p1 == q[t].p2 && q[t].p1 == q[t].p3){
                    printf("%d\n", q[t].st); return;
                } 
            }
        
        for (int i = 1; i <= n; i++)
            if (!f[q[s].p1][q[s].p2][i] && c[q[s].p3][i] == c[q[s].p1][q[s].p2]){
                q[++t] = Node(q[s].p1, q[s].p2, i, q[s].st + 1);
                f[q[s].p1][q[s].p2][i] = 1;
                if (q[t].p1 == q[t].p2 && q[t].p1 == q[t].p3){
                    printf("%d\n", q[t].st); return;
                }
            }   
        s++;
    }
    puts("impossible");   
}

int main(){
    char ts[5];
    while (scanf("%d", &n) != EOF && n){
        scanf("%d %d %d", &q[0].p1, &q[0].p2, &q[0].p3);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++){
                scanf("%s", ts);
                c[i][j] = ts[0];     
            }  
        solve();
    }
    return 0;   
}