[TIOJ]1111. [入門] Crucio

題目連結：http://tioj.ck.tp.edu.tw/problems/1111

判斷不少的DFS題。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int n;
string s[505];
int ans[5];
int gx[8] = {1,0,-1,0,1,1,-1,-1},gy[8] = {0,1,0,-1,1,-1,1,-1};
bool is(int l,int r,int ll,int rr){
    if(ll < 0 || ll >= n || rr < 0 || rr >= n)return 1;
    return s[l][r] != s[ll][rr];
}
int DFS(int x,int y,int st,int f){
    if(st == 1){
        int tmp = 0;
        for(int i = 0 ; i < 8 ; i++){
            int xx = x+gx[i],yy = y+gy[i];  
            if(xx < n && xx >= 0 &&yy < n && yy >= 0&&s[xx][yy] == s[x][y] && is(x,y,x-gx[i],y-gy[i])){
                tmp += DFS(xx,yy,st+1,i);
            }
        }
        return tmp;
    }int t = x+gx[f],p = y+gy[f];
    if(st == 5){
        if(t < n && t >= 0 &&p < n && p >= 0 && s[t][p] == s[x][y])return 0;
        return 1;
    }if(t < n && t >= 0 &&p < n && p >= 0 && s[t][p] == s[x][y])return DFS(t,y+gy[f],st+1,f);
    return 0;
}
int main(){cin.tie(0);ios_base::sync_with_stdio(0);
    while(cin >> n,n){
        fill(ans,ans+5,0);
        for(int i = 0 ; i < n ; i++)cin >> s[i];
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                if(s[i][j] == '.')continue;
                ans[s[i][j]-'A'] += DFS(i,j,1,-1);
            }
        }
        for(int i = 0 ; i < 3; i++)cout << (char)('A'+i) << ' '<< ans[i]/2 << endl;
        cout <<endl;
    }
    return 0;
}