敌对搜索

模板题

XDOJ-1045-黑白棋

#include <iostream>
using namespace std;

const int N = 7;
int dirx[4] = { -1, 1, 0, 0 };
int diry[4] = { 0, 0, -1, 1 };
int a[N][N];

bool dfs (int x, int y) { // 先手落子于 (x, y) 处是否必胜
    a[x][y] = 1;
    for (int i = 0; i < 4; ++ i) {
        int nx = x + dirx[i], ny = y + diry[i];
        if (a[nx][ny] == 1) continue;
        if (dfs(nx, ny) == true) {
            a[x][y] = 0; // 还原
            return false; // 必败
        }
    }
    a[x][y] = 0; // 还原
    return true; // 必胜
}

int main () {
    for (int i = 0; i <= 6; ++ i) { // 边界
        a[0][i] = a[6][i] = 1;
        a[i][0] = a[i][6] = 1;
    }
    int T;
    scanf("%d", &T);
    while (T --) {
        for (int i = 1; i <= 5; ++ i)
            for (int j = 1; j <= 5; ++ j)
                scanf("%1d", &a[i][j]);
        
        bool flag = false;
        for (int i = 1; i <= 5; ++ i) {
            for (int j = 1; j <= 5; ++ j) {
                if (a[i][j] == 1) continue;
                if (dfs(i, j) == true) {
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        printf(flag == true ? "win\n" : "lose\n");
    }
    return 0;
}