1443: [JSOI2009]游戏Game
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 557 Solved: 251
[Submit][Status]
Description
Input
输入数据首先输入两个整数N,M,表示了迷宫的边长。 接下来N行,每行M个字符,描述了迷宫。
Output
若小AA能够赢得游戏,则输出一行"WIN",然后输出所有可以赢得游戏的起始位置,按行优先顺序输出 每行一个,否则输出一行"LOSE"(不包含引号)。
Sample Input
3 3
.##
...
#.#
.##
...
#.#
Sample Output
2 3
3 2
3 2
HINT
对于100%的数据,有1≤n,m≤100。
对于30%的数据,有1≤n,m≤5。
Source
代码:
View Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #define rep(i,n) for (int i=1;i<=n;i++) 6 #define num(i,j) (i-1)*m+j 7 8 using namespace std; 9 10 const int N=105; 11 const int d[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; 12 char map[N][N]; 13 int ans[N],n,m,i,j,nx,ny,cnt,tot,linker[N*N],tmp[N*N],g[N*N][5]; 14 bool v[N*N],fail[N*N],black[N*N],flag; 15 16 void init() 17 { 18 scanf("%d%d",&n,&m); 19 rep(i,n) scanf("%s",map[i]+1); 20 rep(i,n)rep(j,m) 21 { 22 if (map[i][j]==‘#‘) {fail[num(i,j)]=1;continue;} 23 if ((i+j)%2==0) black[num(i,j)]=1; 24 for (int k=0;k<4;k++) 25 { 26 nx=i+d[k][0];ny=j+d[k][1]; 27 if (nx<1||nx>n||ny<1||ny>m||map[nx][ny]==‘#‘) continue; 28 int u=num(i,j),v=num(nx,ny); 29 g[u][++g[u][0]]=v; 30 } 31 } 32 } 33 34 int dfs(int x) 35 { 36 rep(i,g[x][0]) 37 { 38 int t=g[x][i]; 39 if (v[t]) continue; 40 v[t]=1; 41 if (linker[t]==0||dfs(linker[t])) 42 { 43 linker[t]=x; 44 linker[x]=t; 45 return 1; 46 } 47 } 48 return 0; 49 } 50 51 void dawn() 52 { 53 for (int i=1;i<=n*m;i++) if (!fail[i]&&black[i]) 54 { 55 memset(v,0,sizeof(v)); 56 if (dfs(i)) cnt++; 57 } 58 flag=1; 59 rep(i,n*m) if (!fail[i]) 60 { 61 memset(v,0,sizeof(v)); 62 v[i]=1; 63 if (!linker[i]||dfs(linker[i])) 64 { 65 tot++; 66 if (flag) puts("WIN"),flag=0; 67 linker[i]=0,printf("%d %d\n",(i-1)/m+1,(i-1)%m+1); 68 } 69 } 70 if (!tot) puts("LOSE"); 71 } 72 73 int main() 74 { 75 //freopen("1.txt","r",stdin); 76 //freopen("2.txt","w",stdout); 77 init(); 78 dawn(); 79 //while (1); 80 }
--lyd
貌似整个算法的流程是:
1.黑白染色
2.对黑、白进行二分图最大匹配
3.枚举每一个可达点,若该点可不再最大匹配中,则输出该点
…………
Is this ok? 反正AC了,原理在哪里?这样就行了?