1443: [JSOI2009]游戲Game

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?1077??Solved:?484
[Submit][Status][Discuss]

Description

Input

輸入數(shù)據(jù)首先輸入兩個(gè)整數(shù)N,M，表示了迷宮的邊長。 接下來N行，每行M個(gè)字符，描述了迷宮。

Output

若小AA能夠贏得游戲，則輸出一行"WIN"，然后輸出所有可以贏得游戲的起始位置，按行優(yōu)先順序輸出 每行一個(gè),否則輸出一行"LOSE"（不包含引號）。

Sample Input

3 3
.##
...
#.#

Sample Output

WIN
2 3
3 2

HINT

?

對于100%的數(shù)據(jù)，有1≤n,m≤100。 對于30%的數(shù)據(jù)，有1≤n,m≤5。

?

Source

分析：

這是一個(gè)網(wǎng)格圖，然后每個(gè)狀態(tài)只能向相鄰的狀態(tài)轉(zhuǎn)移，并且輸贏和路徑長度的奇偶性有關(guān)系，所以考慮黑白染色，也就是狀態(tài)只能向不同的顏色轉(zhuǎn)移，那么就是一個(gè)二分圖...

如果二分圖求完最大匹配之后不存在非匹配點(diǎn)，那么一定不存在必勝策略，因?yàn)槲覀兦笸曜畲笃ヅ渲?#xff0c;一定不存在增廣路，只存在交錯(cuò)路，對方從匹配點(diǎn)出發(fā)，最后一定可以找到一條匹配邊作為結(jié)束，所以先手必勝...

那么也就是說，從一個(gè)非匹配點(diǎn)出發(fā)，一定是一個(gè)后手必勝的策略，但是非匹配點(diǎn)并不是全部答案，因?yàn)椴⒉皇侵荡嬖谝唤M最大匹配，所以從每個(gè)非匹配點(diǎn)出發(fā)，尋找交錯(cuò)路，然后訪問到的和非匹配點(diǎn)處于同一集合的點(diǎn)都是答案...

代碼：

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> //by NeighThorn using namespace std;const int maxn=200+5,maxm=20000+5;int n,m,cnt,tot,f[maxn][maxn],hd[maxm],to[maxm<<1],nxt[maxm<<1]; int pre[maxm],vis[maxm],co[maxm],ans[maxm]; int mv[2][2]={0,1,1,0};char mp[maxn][maxn];inline void add(int x,int y){to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++; }inline bool dfs(int x){for(int i=hd[x];i!=-1;i=nxt[i])if(!vis[to[i]]){vis[to[i]]=1;if(pre[to[i]]==-1||dfs(pre[to[i]])){return pre[to[i]]=x,true;}}return false; }inline void find(int x){if(ans[x])return;ans[x]=1;for(int i=hd[x];i!=-1;i=nxt[i])if(pre[to[i]]!=-1)find(pre[to[i]]); }signed main(void){scanf("%d%d",&n,&m);memset(hd,-1,sizeof(hd));memset(pre,-1,sizeof(pre));for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]=='.')f[i][j]=++tot,co[f[i][j]]=(i^j)&1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]=='.') for(int k=0;k<2;k++){int x=i+mv[k][0],y=j+mv[k][1];if(f[x][y])add(f[i][j],f[x][y]),add(f[x][y],f[i][j]);}for(int i=1;i<=tot;i++)if(co[i])memset(vis,0,sizeof(vis)),cnt+=dfs(i);if(cnt*2==tot){puts("LOSE");return 0;}puts("WIN");for(int i=1;i<=tot;i++)if(pre[i]!=-1)pre[pre[i]]=i;for(int i=1;i<=tot;i++)if(pre[i]==-1)find(i);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(ans[f[i][j]])printf("%d %d\n",i,j);return 0; }

　　

---

By NeighThorn

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

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1443: [JSOI2009]游戏Game的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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