1971兔兔与蛋蛋题解

· · 题解

1971兔兔与蛋蛋

二分图博弈论

author: LiveDream

前置知识:

  1. 对于二分图博弈，先手如果率先落入最大匹配的点x中，那么后手只需要选择与x匹配的点y走即可，走到最后先手必败；
  2. 如果是完全匹配，那么先手无论落子何处，均率先落入最大匹配点，先手必败；
  3. 如果不是完全匹配，先手选择非最大匹配点x落子，那么后手无论落子何处，都是最大匹配中的某点y， 因为如果y不是最大匹配的点, 则x到y形成增广路，最大匹配的边数还可以加1，导致矛盾；进而， 后手率先落入最大匹配的点中，先手有必胜策略；

本题策略：

  1. 把棋子的移动视为空格的移动，那么兔兔先手移动空格到白子处，因此可以将空格看作黑色， 黑白染色，建二分图；
  2. 如果在移动空格前，空格处于最大匹配的非必须点，那么移动后必然率先进入最大匹配中，必败，反之有必胜策略；
  3. 对于K轮游戏，第i轮游戏时空格的位置cur在(sx, sy), 如果cur不在最大匹配中，那么落子后必落入最大匹配， 所以无论怎么落子，必败；
  4. 如果cur在最大匹配中,且有匹配match[cur]为nxt，那么删掉cur后从nxt跑匈牙利，看nxt是否还能有另外的匹配，如果有 那么cur就不是最大匹配的必须点，有必胜策略，反之仍然必败；对每1轮游戏重复操作，得到每1轮游戏的胜负情况win[i]；
  5. 如何判断兔兔犯了错误？——如果win[i]是必胜，而兔兔走完之后win[i+1]必胜，那么就说明兔兔犯了错； 
#include<iostream>
#include<cstring>
using namespace std;
const int N = 50, K = 1005;
int n, m, ans, cnt, tot, head[N*N];
char g[N][N];
int match[N*N], res[K*2], win[K*2]; 
bool vis[N*N], block[N*N], color[N][N];
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
struct node 
{
    int to, nxt;
}edge[N*N*2*4]; //每个点连4个方向，双向边 

void addedge(int s, int e) 
{
    cnt++;
    edge[cnt].to = e;
    edge[cnt].nxt = head[s];
    head[s] = cnt;
    return ;
}

bool dfs(int x) //匈牙利算法
{
    for(int i = head[x]; i != 0; i = edge[i].nxt) 
    {
        int y = edge[i].to;
        if(block[y] == true) //添加一行屏蔽已删掉的点 
            continue;
        if(vis[y] == false) 
        {
            vis[y] = true;
            //如果y没有匹配 或者 y的匹配点match[y]能找到一个新的匹配
            if(match[y] == 0 || dfs(match[y]) == true) 
            {
                match[y] = x; //y的配对点是x
                match[x] = y; //增加这行代码的原因是为了找最大匹配非必须点
                return true;
            }
        }
    }
    return false;
}

int get_id(int x, int y)
{
    return (x-1) * m + y;
} 

bool check(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > m || color[x][y] == false)
        return false;
    return true;    
}

int main()
{
    //输入 
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> g[i][j]; //迷宫数组 
    //染色
    int sx, sy;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(g[i][j] == 'O') //将白色的棋子染色 
            {
                color[i][j] = true;
            }
            else if(g[i][j] == '.') //起点记录，当作黑色对待 
            {
                sx = i;
                sy = j;
            }
        }
    //建图 
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(color[i][j] == true) //白子跳过 
                continue;
            int cur = get_id(i, j); //当前点编号 
            for(int k = 0; k < 4; k++)
            {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if(check(nx, ny) == false)
                    continue;
                int nxt = get_id(nx, ny);
                addedge(cur, nxt); //建边 
                addedge(nxt, cur); //找最大匹配不需要反边，但是找最大匹配非必须点需要折返跑 
            }
        }
    //匈牙利, 目的是看起点是否落在最大匹配中 
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(color[i][j] == false)
                continue;
            memset(vis, 0, sizeof(vis));
            int cur = get_id(i, j); 
            if(dfs(cur) == true) 
                ans++;
        }
    //输入游戏过程 
    int k; 
    cin >> k;
    for(int i = 1; i <= 2*k; i++)
    {
        int cur = get_id(sx, sy);
        block[cur] = true; //删掉cur 
        if(match[cur] == 0) //棋子当前不在匹配中，那么下一步会率先走到最大匹配中，必败 
            win[i] = false;
        else
        {
            int nxt =  match[cur];
            match[cur] = match[nxt] = 0;  //删掉cur与 nxt的匹配关系 
            memset(vis, 0, sizeof(vis)); //跑匈牙利记得清0 vis 
            if(dfs(nxt) == true) //若nxt还能找到匹配，则cur不是最大匹配必须, 那么下一步率先走到最大匹配，必败 
                win[i] = false;
            else
                win[i] = true; 
        }
        cin >> sx >> sy;
    }

    //处理输出 
    for(int i = 1; i <= k; i++) 
    {
        if(win[2*i-1] == true && win[2*i] == true) //兔兔走之前是有必胜策略，走完蛋蛋有必胜策略 
        {
            res[++tot] = i; 
        }
    }
    cout << tot << endl;
    for(int i = 1; i <= tot; i++)
    {
        cout << res[i] << endl;
    }
    return 0;
}