首页 > 代码库 > JSOI2009 游戏

JSOI2009 游戏

2024-07-12 15:32:38   219人阅读

1443: [JSOI2009]游戏Game

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 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

HINT

对于100%的数据，有1≤n,m≤100。 
对于30%的数据，有1≤n,m≤5。

Source

JSOI2009Day2

代码：
 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 }
View Code

--lyd

貌似整个算法的流程是：

1.黑白染色

2.对黑、白进行二分图最大匹配

3.枚举每一个可达点，若该点可不再最大匹配中，则输出该点

…………

Is this ok? 反正AC了，原理在哪里？这样就行了？


联系
我们