HDU 4101 Ali and Baba （思路好题）

与其说这是个博弈，倒不如说是个搜索。这题思路不错，感觉很难把情况考虑周全。

在地图外围填充一圈0，两次BFS，第一次从-1点出发，把从-1到达的0点以及包围0的那一圈石头标记出来。如下图：

6 7
1  1  1  1  1  1  1
1  0  0  0  0  0  1
1  0  3  5  1  1  1
1  0 -1  4  0  1  1
1  0  1  0  0  1  1
1  1  1  1  1  1  1

第二次BFS，从外围（0,0）点出发，找出外面与标记石头的交界层：

6 7
1  1  1  1  1  1  1
1  0  0  0  0  0  1
1  0  3  5  1  1  1
1  0 -1  4  0  1  1
1  0  1  0  0  1  1
1  1  1  1  1  1  1

实际上起决定性作用的只有红色的那一圈和那一圈外的石头HP和，里面的石头HP不影响结果。

之前我的BFS只能处理这种情况（如下），就是里面的石头跟外面的那一圈石头是不相连的，却无法处理上面那两种情况（把绿色的3，5，1，4也加上了），所以一直WA……

7 7
1  1  1  1  1  1  1
1  0  0  0  0  0  1
1  0  1  0  0  0  1 
1  0  0  0  0  0  1
1  0 -1  0  0  0  1
1  0  0  0  0  0  1
1  1  1  1  1  1  1

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>

using namespace std;

const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };

const int MAXN = 310;

struct Point
{
    int x, y;
    Point( int x = 0, int y = 0 ):x(x), y(y) {}
};

bool vis[MAXN][MAXN];
int G[MAXN][MAXN];
bool flag[MAXN][MAXN];
int M, N;
Point st;
int sum;
int ok;

void BFS()
{
    ok = 0;
    queue<Point> Q;
    Q.push( st );
    memset( vis, false, sizeof(vis) );
    memset( flag, false, sizeof(flag) );
    vis[st.x][st.y] = true;
    flag[st.x][st.y] = true;
    while ( !Q.empty() )
    {
        Point cur = Q.front();
        Q.pop();
        if ( cur.x == 1 || cur.x == N || cur.y == 1 || cur.y == M ) ok = 1;
        for ( int i = 0; i < 4; ++i )
        {
            int xx = cur.x + dx[i];
            int yy = cur.y + dy[i];
            if ( xx >= 1 && xx <= N && yy >= 1 && yy <= M )
            {
                if ( !vis[xx][yy] )
                {
                    vis[xx][yy] = true;
                    flag[xx][yy] = true;
                    if ( G[xx][yy] == 0 )
                        Q.push( Point( xx, yy ) );
                }
            }
        }
    }
    return;
}

void BFS2( Point stt )
{
    queue<Point> Q;
    memset( vis, false, sizeof(vis) );
    Q.push( stt );
    vis[0][0] = true;

    while ( !Q.empty() )
    {
        Point p = Q.front();
        Q.pop();
        vis[ p.x ][ p.y ] = true;
        sum += G[p.x][p.y];
        //printf( "%d %d %d
", p.x, p.y, G[p.x][p.y] );
        for ( int i = 0; i < 4; ++i )
        {
            int xx = p.x + dx[i];
            int yy = p.y + dy[i];
            if ( xx >= 0 && xx <= N+1 && yy >= 0 && yy <= M+1 && !vis[xx][yy] )
            {
                vis[xx][yy] = true;
                if ( !flag[xx][yy] ) Q.push( Point( xx, yy ) );
                else sum += G[xx][yy] - 1;
            }
        }
    }
    return;
}

int main()
{
    while ( scanf( "%d%d", &N, &M ) == 2 )
    {
        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] == -1 ) st = Point( i, j );
            }

        BFS();
        if ( ok )
        {
            puts("Ali Win");
            continue;
        }
        sum = 0;
        BFS2( Point(0, 0) );
        //printf( "sum=%d
", sum );
        if ( sum % 2 == 0 ) puts("Baba Win");
        else puts("Ali Win");
    }
    return 0;
}