2437: [Noi2011]兔兔与蛋蛋
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 678 Solved: 429
[Submit][Status][Discuss]
Description
Input
输入的第一行包含两个正整数 n、m。
接下来 n行描述初始棋盘。其中第i 行包含 m个字符，每个字符都是大写英文字母"X"、大写英文字母"O"或点号"."之一，分别表示对应的棋盘格中有黑色棋子、有白色棋子和没有棋子。其中点号"."恰好出现一次。
接下来一行包含一个整数 k（1≤k≤1000） ，表示兔兔和蛋蛋各进行了k次操作。
接下来 2k行描述一局游戏的过程。其中第 2i – 1行是兔兔的第 i 次操作（编号为i的操作） ，第2i行是蛋蛋的第i次操作。每个操作使用两个整数x,y来描述，表示将第x行第y列中的棋子移进空格中。
输入保证整个棋盘中只有一个格子没有棋子， 游戏过程中兔兔和蛋蛋的每个操作都是合法的，且最后蛋蛋获胜。
Output
输出文件的第一行包含一个整数r，表示兔兔犯错误的总次数。
接下来r 行按递增的顺序给出兔兔“犯错误”的操作编号。其中第 i 行包含一个整数ai表示兔兔第i 个犯错误的操作是他在游戏中的第 ai次操作。
1 ≤n≤ 40， 1 ≤m≤ 40
Sample Input
样例一：
1 6
XO.OXO
1
1 2
1 1
样例二：
3 3
XOX
O.O
XOX
4
2 3
1 3
1 2
1 1
2 1
3 1
3 2
3 3
样例三：
4 4
OOXX
OXXO
OO.O
XXXO
2
3 2
2 2
1 2
1 3
1 6
XO.OXO
1
1 2
1 1
样例二：
3 3
XOX
O.O
XOX
4
2 3
1 3
1 2
1 1
2 1
3 1
3 2
3 3
样例三：
4 4
OOXX
OXXO
OO.O
XXXO
2
3 2
2 2
1 2
1 3
Sample Output
样例一：
1
1
样例二：
0
样例三：
2
1
2
样例1对应图一中的游戏过程
样例2对应图三中的游戏过程
1
1
样例二：
0
样例三：
2
1
2
样例1对应图一中的游戏过程
样例2对应图三中的游戏过程
HINT
Source
分析：
和BZOJ 1443是一样的...
把空格看成黑点，然后就转化成了BZOJ 1443...
如果决策错误就代表从一个必胜态转移到了另一个必胜态，然后做完一个决策就把前一次空格所在位置的点删去，不断寻找最大匹配...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
const int maxn=40+5,maxm=1600+5,maxk=1000+5;
int hd[maxm],to[maxm<<1],nxt[maxm<<1];
int n,m,k,cnt,tot,f[maxn][maxn],co[maxm],mv[2][2]={0,-1,-1,0};
int c,ans,stx,sty,sta,is[maxm],pre[maxm],vis[maxm],del[maxm],res[maxk<<1];
char mp[maxn][maxn];
inline bool judge(char x){
if(x=='X'||x=='.')
return 1;
return 0;
}
inline void add(int x,int y){
to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;
}
inline bool dfs(int x){
if(del[x])
return false;
for(int i=hd[x];i!=-1;i=nxt[i])
if(!vis[to[i]]&&!del[to[i]]){
vis[to[i]]=1;
if(pre[to[i]]==-1||dfs(pre[to[i]]))
return pre[x]=to[i],pre[to[i]]=x,true;
}
return false;
}
signed main(void){
// freopen("out.txt","w",stdout);
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 j=1;j<=m;j++)
if(mp[i][j]=='.')
c=((i^j)&1)^1,stx=i,sty=j;
}
scanf("%d",&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
f[i][j]=++tot;co[f[i][j]]=((i^j)&1)^c;is[tot]=1;
if(co[f[i][j]]==judge(mp[i][j]))
for(int t=0;t<2;t++){
int x=i+mv[t][0],y=j+mv[t][1];
if(f[x][y])
add(f[i][j],f[x][y]),add(f[x][y],f[i][j]);
}
else
f[i][j]=0,is[tot]=0;
}
for(int i=1;i<=tot;i++)
if(is[i]&&co[i])
memset(vis,0,sizeof(vis)),dfs(i);
for(int i=1;i<=k<<1;i++){
int x=f[stx][sty],y=pre[x];del[x]=1;
if(y!=-1){
pre[x]=pre[y]=-1;
memset(vis,0,sizeof(vis));
if(!dfs(y))
res[i]=1;
else
res[i]=0;
}
else
res[i]=0;
scanf("%d%d",&stx,&sty);
}
for(int i=1;i<=k<<1;i+=2)
if(res[i]&&res[i+1])
ans++;
printf("%d
",ans);
for(int i=1;i<=k<<1;i+=2)
if(res[i]&&res[i+1])
printf("%d
",(i+1)>>1);
return 0;
}
By NeighThorn