Ali and Baba

3 3
1 1 1
1 -1 1
1 1 1

Baba Win

题意：给一个矩阵，0表示空的可走，-1宝藏的位置（仅仅有一个），其余的正整数表示该位置石头数。甲乙两个人，轮流玩游戏。甲先玩，轮到Ａ走的时候，宝藏和外面有一条路，则Ａ获胜。假设不能直接到达宝藏位置，能够从外面通过空到某个位置，拿走该位置上的一个石头，假设该位置没有石头则变成空的可走。

思路：找到包围宝藏的圈，然后统计圈外面有多少石头（圈上的石头变为１），假设为奇数，则Ali Win，否则Baba Win

先从宝藏ＢＦＳ找到圈边界，假设能够到达外面，则Ali Win，否则，从外面ＢＦＳ，假设是圈边界，则cnt+=n-1;否则假设是石头，则所有统计。然后推断奇偶；

遇到的问题：

刚開始思路错误，開始是直接统计圈里面多少石头，然后减去，然后推断奇偶。

ＮＭ范围看错了。看成了100

由于第二个BFS是复制的第一个BFS，导致里面有些错误没有注意到！！比方　应该是nx 结果是ｘ　导致ＷＡ了非常久

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <set>

using namespace std;

//#define WIN
#ifdef WIN
typedef __int64 LL;
#define iform "%I64d"
#define oform "%I64d\n"
#define oform1 "%I64d"
#else
typedef long long LL;
#define iform "%lld"
#define oform "%lld\n"
#define oform1 "%lld"
#endif

#define S64I(a) scanf(iform, &(a))
#define P64I(a) printf(oform, (a))
#define S64I1(a) scanf(iform1, &(a))
#define P64I1(a) printf(oform1, (a))
#define FOR(i, s, t) for(int (i)=(s); (i)<(t); (i)++)

const int INF = 0x3f3f3f3f;
const double eps = 10e-9;
const double PI = (4.0*atan(1.0));

const int maxn = 300 + 20;
const int moveX[] = {-1, 1, 0, 0};
const int moveY[] = {0, 0, -1, 1};
int G[maxn][maxn];
int TG[maxn][maxn];
int vis[maxn][maxn];
int n, m;

struct Node {
    int x, y;
    Node(int xx=0, int yy=0) {
        x = xx;
        y = yy;
    }
};

queue<Node> Q;
int bfs(int sx, int sy) {
    memset(TG, 0, sizeof(TG));
    memset(vis, 0, sizeof(vis));
    while(!Q.empty()) Q.pop();
    Q.push(Node(sx, sy));
    vis[sx][sy] = 1;
    int res = 0;
    while(!Q.empty()) {
        int x = Q.front().x;
        int y = Q.front().y;
        Q.pop();
        for(int i=0; i<4; i++) {
            int nx = x + moveX[i];
            int ny = y + moveY[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m) return 1;
            if(vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            if(G[nx][ny] > 0) {TG[nx][ny] = 1;}
            else Q.push(Node(nx, ny));
        }
    }
    return 0;
}

int bfs1(int sx, int sy) {
    memset(vis, 0, sizeof(vis));
    while(!Q.empty()) Q.pop();
    Q.push(Node(sx, sy));
    vis[sx][sy] = 1;
    int res = 0;
    while(!Q.empty()) {
        int x = Q.front().x;
        int y = Q.front().y;
        Q.pop();
        for(int i=0; i<4; i++) {
            int nx = x + moveX[i];
            int ny = y + moveY[i];
            if(nx < 0 || nx > n+1 || ny < 0 || ny > m+1) continue;
            if(vis[nx][ny]) continue;
            vis[nx][ny] = 1;
            if(TG[nx][ny] == 1) {
                res += G[nx][ny] - 1;
                //printf("%d %d -> %d = %d\n", nx, ny, G[nx][ny]-1, res);
            } else {
                Q.push(Node(nx, ny));
                if(G[nx][ny] > 0) res += G[nx][ny];
                //if(G[nx][ny] > 0) printf("%d %d -> %d = %d\n", nx, ny, G[nx][ny], res);
            }   
        }
    }
    return res;
}

int main() {

    while(scanf("%d%d", &n, &m) != EOF) {
        if(!n || !m) while(1);
        /*if(!n || !m) {
            puts("Ali Win");
            continue;
        }*/
        int sum = 0;
        int sx, sy;
        memset(G, 0, sizeof(G));
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                scanf("%d", &G[i][j]);
                if(G[i][j] > 0) sum += G[i][j];
                if(G[i][j] == -1) {
                    sx = i;
                    sy = j;
                }
            }
        }
        int t = bfs(sx, sy);
        if(t) {
            puts("Ali Win");
            continue;
        }
        t = bfs1(0, 0);
        //printf("-->%d\n", t);
        if(t&1) puts("Ali Win");
        else puts("Baba Win");
    }

    return 0;
}