Round F 2020 - Kick Start 2020

题意：有一张这样子的图，有公共边的两个格子看做相邻。有一些格子是坏的不能通过。Alice从(Ra, Pa)出发，Bob从(Rb, Pb)出发。Alice先手，路过的格子被刷漆，直到两个人都没有路可走，游戏结束。最终的分数为Alice刷的格子的数量 - Bob刷的格子的数量。 Alice每次移动的时候想让最终的分数尽量大，Bob想让最终的分数尽量小，每个人每次移动都执行最佳策略，问最后Alice能够保证的最大分数是多少。

---

思路：博弈搜索，每次Alice移动的时候，如果最后得到的分数比当前的分数要大，则接收这次移动。Bob移动的时候，如果最后得到的分数比当前的分数要小，则接收这次移动。

---

代码：

#include <stdio.h>

#include <iostream>

#include <map>

#include <vector>

using namespace std;

map<pair<int, int>, int> mp;

//0 broken, 1 unpainted, 2 painted

int a[5] = {0, -1, 0, 0, 1};

int b[5] = {0, -1, -1, 1, 1};

int N;

int Ra, Pa, Rb, Pb, S;

pair<int, int> dfs(int ax, int ay, int bx, int by, int flag, int ok){

    int x, y;

    bool find = false;

    //cout << ax << " " << ay << " " << bx << " " << by << endl;

    if(flag == 0){

        x = ax;

        y = ay;

    }else{

        x = bx;

        y = by;

    }

    pair<int, int> ans = {-1, -1};

    for(int i = 1; i <= 4; i++) {

        if ((y % 2 == 1 && i == 1) || (y % 2 == 0 && i == 4))  continue;

        int tx = x + a[i];

        int ty = y + b[i];

        if (tx < 1 || tx > N || ty < 1 || ty > tx * 2 - 1 || mp[make_pair(tx, ty)] != 1) continue;

        find = true;

        mp[make_pair(tx, ty)] = 2;

        if(!flag) {

            //Alice's turn

            pair<int, int> num = dfs(tx, ty, bx, by,flag ^ 1, find);

            if(ans.first == -1 && ans.second == -1) ans = num;

            else if(num.first - num.second > ans.first - ans.second) ans = num;

        }else{

            //Bob's turn

            pair<int, int> num = dfs(ax, ay, tx, ty,flag ^ 1, find);

            if(ans.first == -1 && ans.second == -1) ans = num;

            else if(num.first - num.second < ans.first - ans.second) ans = num;

        }

        mp[make_pair(tx, ty)] = 1;

    }

    if(!find && !ok) return make_pair(0, 0);

    if(!find){

        pair<int,int> num;

        num = dfs(ax, ay, bx, by,flag ^ 1,0);

        return {num.first, num.second};

    }

    if(flag) return make_pair(ans.first, ans.second + 1);

    else return make_pair(ans.first + 1, ans.second);

}

int main(){

    int T;

    cin >> T;

    for(int t = 1; t <= T; t++){

        mp.clear();

        cin >> N >> Ra >> Pa >> Rb >> Pb >> S;

        for(int i = 1; i <= N; i++){

            for(int j = 1; j <= 2 * i - 1; j++){

                mp[make_pair(i, j)] = 1;

            }

        }

        mp[make_pair(Ra, Pa)] = 2;

        mp[make_pair(Rb, Pb)] = 2;

        for(int i = 0; i < S; i++){

            int ta, tb;

            cin >> ta >> tb;

            mp[make_pair(ta, tb)] = 0;

        }

        pair<int, int> res = dfs(Ra, Pa, Rb, Pb, 0, 1);

        printf("Case #%d: %d\n", t, res.first - res.second);

    }

}