傳送門

結論 不會有同一個棋子移動兩次

反證法，對于第一個移動第二次的棋子

設兩次移動之間(含)的移動的棋子為$A_1,A_2,A_3,\dots \dots ，A_n$（指棋子本身而非位置）

因為最后移回來了，所以往上和往下、往左和往右次數相同

所以$n$是偶數 然后$A_1$和$A_n$顏色不同

但這個棋子開始被移到當前位置，最后被移走，所以$A_1=A_n$，矛盾

所以移動路徑沒有交

既然這樣，我們就不用考慮棋盤具體的變化，而看成空格交替走兩個顏色

然后和上一道題就一樣了

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 2005 #define MAXM 10005 using namespace std; struct edge{int u,v;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt; void addnode(int u,int v) {e[++cnt]=(edge){u,v};nxt[cnt]=head[u];head[u]=cnt; } int n,m; #define id(x,y) (((x)-1)*m+(y)) char s[50][50]; const int dx[]={-1,1,0,0},dy[]={0,0,-1,1}; bool del[MAXN]; int link[MAXN],used[MAXN]; bool find(int u) {for (int i=head[u];i;i=nxt[i])if (!used[e[i].v]&&!del[e[i].v]){used[e[i].v]=1;if (!del[link[e[i].v]]&&(!link[e[i].v]||find(link[e[i].v]))){link[u]=e[i].v,link[e[i].v]=u;return true;}}return false; } int calc() {memset(link,0,sizeof(link));int ans=0;for (int x=1;x<=n;x++)for (int y=1;y<=m;y++)if (s[x][y]!='O'&&!del[id(x,y)])memset(used,0,sizeof(used)),ans+=find(id(x,y));return ans; } bool win[MAXN]; int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%s",s[i]+1);int st;for (int x=1;x<=n;x++)for (int y=1;y<=m;y++)if (s[x][y]!='O'){for (int i=0;i<4;i++)if (s[x+dx[i]][y+dy[i]]=='O')addnode(id(x,y),id(x+dx[i],y+dy[i]));if (s[x][y]=='.') st=id(x,y);}int k,tot=0;scanf("%d",&k);int mmat=calc();for (int i=1;i<=2*k;i++){del[st]=1;int t=calc();if (mmat!=t) win[i]=1;mmat=t;int x,y;scanf("%d%d",&x,&y);st=id(x,y);}for (int i=1;i<=k;i++) if (win[2*i-1]&&win[2*i]) ++tot;printf("%d\n",tot);for (int i=1;i<=k;i++) if (win[2*i-1]&&win[2*i]) printf("%d\n",i); return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。