題面

題面

題解

通過觀察，我們可以發(fā)現(xiàn)如下性質(zhì)：

• 可以看做是2個(gè)人在不斷移動(dòng)空格，只是2個(gè)人能移動(dòng)的邊不同
• 一個(gè)位置不會(huì)被重復(fù)經(jīng)過 ： 根據(jù)題目要求，因?yàn)槭前春诎纵喠髯?#xff0c;所以不可能重復(fù)經(jīng)過一個(gè)點(diǎn)，不然就變成一個(gè)人連續(xù)走2次了
• 原圖是一個(gè)二分圖 ： 也是由按黑白輪流走這個(gè)要求得到的
  因此我們對原圖按照與原點(diǎn)的距離進(jìn)行黑白染色，再跑二分圖博弈即可。

#include<bits/stdc++.h> using namespace std; #define R register int #define AC 45 #define ac 5000int n, m, sx, sy, all; int id[AC][AC], ans[ac], link[ac]; int a[6] = {-1, 1, 0, 0}, b[6] = {0, 0, -1, 1}; bool can[AC][AC], z[ac], vis[ac]; char s[AC][AC];struct node{int x, y;}back[ac];inline int read() {int x = 0;char c = getchar();while(c > '9' || c < '0') c = getchar();while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x; }bool check(int x, int y)//起點(diǎn)是黑色 {int tmp = abs(x - sx) + abs(y - sy);if((tmp & 1) && s[x][y] == 'O') return 1;//相距奇數(shù)格，則為白格，需要白色else if(!(tmp & 1) && s[x][y] == 'X') return 1;else if(s[x][y] == '.') return 1;return 0; }bool dfs(int x) {for(R i = 0; i < 4; i ++){int xx = back[x].x + a[i], yy = back[x].y + b[i], ID = id[xx][yy];if(xx <= 0 || yy <= 0 || xx > n || yy > m) continue;if(!can[xx][yy] || vis[ID]) continue;vis[ID] = true;if(!link[ID] || dfs(link[ID])) {link[ID] = x, link[x] = ID;return true;}}return false; }void cal() {int tmp = (sx + sy) % 2;for(R i = 1; i <= all; i ++){int x = back[i].x, y = back[i].y;if((x + y) % 2 != tmp || !can[x][y]) continue;//和為奇數(shù)則在T集合memset(vis, 0, sizeof(vis)), dfs(i);} }bool dfs1(int x) {for(R i = 0; i < 4; i ++){int xx = back[x].x + a[i], yy = back[x].y + b[i], ID = id[xx][yy];if(xx <= 0 || yy <= 0 || xx > n || yy > m) continue;if(!can[xx][yy] || vis[ID]) continue;vis[ID] = true;if(!link[ID] || dfs(link[ID])) return true;}return false; }void pre() {n = read(), m = read(), all = n * m;int tmp1 = 1, tmp2 = 2;for(R i = 1; i <= n; i ++) {scanf("%s", s[i] + 1);for(R j = 1; j <= m; j ++){if(s[i][j] == '.') sx = i, sy = j;if((i + j) & 1) id[i][j] = tmp2, back[tmp2] = (node){i, j}, tmp2 += 2;else id[i][j] = tmp1, back[tmp1] = (node){i, j}, tmp1 += 2;}}for(R i = 1; i <= n; i ++)for(R j = 1; j <= m; j ++) can[i][j] = check(i, j); }void check_() {for(int i = 1; i <= n; i ++) {for(int j = 1; j <= m; j ++) printf("%d ", can[i][j]);printf("\n");}for(R i = 1; i <= n; i ++) {for(R j = 1; j <= m; j ++) printf("%d ", link[id[i][j]]);printf("\n");} }void work() {int T = read() << 1, x, y, ID, tmp; bool done;for(R i = 0; i <= T; i ++){for(R j = 1; j <= all; j ++) z[j] = 0;if(i) x = read(), y = read(), ID = id[x][y];else x = sx, y = sy, ID = id[x][y];can[x][y] = 0;//這個(gè)要在一開始就修改if(!link[ID]) continue;//搜S/T集合中有沒有可到達(dá)的同側(cè)未匹配點(diǎn)來取代它,因?yàn)橹苯铀巡惶奖?#xff0c;所以直接搜對面的匹配點(diǎn)是否可以找到增廣路memset(vis, 0, sizeof(vis));done = dfs(link[ID]);//找到了說明這個(gè)點(diǎn)不是必須點(diǎn)tmp = link[ID];//所以搜這個(gè)點(diǎn)的匹配點(diǎn)是否可以找到對面的一個(gè)未匹配點(diǎn)(反向增廣)if(done) link[ID] = 0;//清空這個(gè)點(diǎn)的匹配，因?yàn)檫@個(gè)點(diǎn)已經(jīng)到過了，所以就不能到達(dá)了,如果已經(jīng)匹配上了就不能改了else if(!done) link[ID] = link[tmp] = 0, ans[i] = true;//沒有可取代點(diǎn)就先手必勝}/*for(R i = 0; i <= T; i ++) printf("%d ", ans[i]);printf("\n");*/int rnt = 0;for(R i = 0; i <= T; i += 2)if(ans[i] == 1 && ans[i + 1] == 1) ++ rnt;printf("%d\n", rnt);for(R i = 0; i <= T; i += 2)if(ans[i] == 1 && ans[i + 1] == 1) printf("%d\n", (i + 2) >> 1); }int main() { // freopen("in.in", "r", stdin);pre();cal();work(); // fclose(stdin);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/ww3113306/p/10341912.html

總結(jié)

以上是生活随笔為你收集整理的[NOI2011]兔兔与蛋蛋游戏 二分图博弈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。