1443: [JSOI2009]游戏Game

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 1334 Solved: 613

[Submit][Status][Discuss]

Description

Input

输入数据首先输入两个整数N,M，表示了迷宫的边长。接下来N行，每行M个字符，描述了迷宫。

Output

若小AA能够赢得游戏，则输出一行"WIN"，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出每行一个,否则输出一行"LOSE"（不包含引号）。

Sample Input

3 3

.##

...

.

Sample Output

WIN

2 3

3 2

HINT

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

题解

黑白染色，可走的点连边，做最大匹配

发现如果先手放到非匹配点上，后手要么无路可走，失败，要么走到匹配点上；如果后手走到匹配点上，先手沿匹配点走，后手要么无路可走，要么走非匹配边，由于不存在增广路，后手走到的一定是一个匹配点。。。。一直这样走下去，发现走的是交替路，由于不存在增广路，交替路的结尾一定是匹配边，后手一定无路可走。此时先手必胜

必胜点即为所有最大匹配方案中的未匹配点

其他点均为必败点（相当于先手走必胜点后，后手不得不走的那个点，因此必败）

怎么求呢？

发现从未匹配点开始，走非匹配边、匹配边后，交换匹配边与非匹配边，匹配合法且最大匹配不变。即我们从每个非匹配点走交替路，然后所有匹配点连过来的点都是答案（即与起点同集合的点）

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
              #include 
             
               #include 
              
               #define min(a, b) ((a) < (b) ? (a) : (b))#define max(a, b) ((a) > (b) ? (a) : (b))#define abs(a) ((a) < 0 ? (-1 * (a)) : (a))template
               
                inline void swap(T &a, T &b){ T tmp = a;a = b;b = tmp;}inline void read(int &x){ x = 0;char ch = getchar(), c = ch; while(ch < '0' || ch > '9') c = ch, ch = getchar(); while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); if(c == '-') x = -x;}const int INF = 0x3f3f3f3f;const int MAXN = 100 + 10;const int dx[4] = {0,0,1,-1};const int dy[4] = {1,-1,0,0};int n, m, hao[MAXN][MAXN], vis1[MAXN * MAXN], vis2[MAXN * MAXN], cnt1, cnt2, lk1[MAXN * MAXN], lk2[MAXN * MAXN], vis[MAXN * MAXN];char s[MAXN][MAXN];struct Edge{ int u,v,nxt; Edge(int _u, int _v, int _nxt){u = _u;v = _v;nxt = _nxt;} Edge(){}}edge[100000];int head[MAXN * MAXN], cnt;inline void insert(int a, int b){ edge[++cnt] = Edge(a,b,head[a]); head[a] = cnt;}int dfs(int x){ for(int pos = head[x];pos;pos = edge[pos].nxt) { int i = edge[pos].v; if(vis[i]) continue; vis[i] = 1; if(lk2[i] == -1 || dfs(lk2[i])) { lk2[i] = x, lk1[x] = i; return 1; } } return 0;} void dfs1(int x){ vis1[x] = 1; for(int pos = head[x];pos;pos = edge[pos].nxt) { int i = edge[pos].v; if(lk2[i] == -1 || vis1[lk2[i]]) continue; dfs1(lk2[i]); }}void dfs2(int x){ vis2[x] = 1; for(int pos = head[x];pos;pos = edge[pos].nxt) { int i = edge[pos].v; if(lk1[i] == -1 || vis2[lk1[i]]) continue; dfs2(lk1[i]); }}int main(){ read(n), read(m); for(int i = 1;i <= n;++ i) scanf("%s", s[i] + 1); for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) if(s[i][j] == '#') continue; else if((i + j & 1)) hao[i][j] = ++ cnt1; else hao[i][j] = ++ cnt2; //左奇右偶 for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) if(s[i][j] == '.' && (i + j) & 1) { for(int k = 0;k < 4;++ k) { int x = i + dx[k], y = j + dy[k]; if(x <= 0 || x > n || y <= 0 || y > m || s[x][y] == '#') continue; insert(hao[i][j], hao[x][y]); } } memset(lk1, -1, sizeof(lk1)); memset(lk2, -1, sizeof(lk2)); for(int i = 1;i <= cnt1;++ i) { memset(vis, 0, sizeof(vis)); dfs(i); } for(int i = 1;i <= cnt1;++ i) if(lk1[i] == -1) dfs1(i); cnt = 0;memset(head, 0, sizeof(head)); for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) if(s[i][j] == '.' && (i + j) & 1) { for(int k = 0;k < 4;++ k) { int x = i + dx[k], y = j + dy[k]; if(x <= 0 || x > n || y <= 0 || y > m || s[x][y] == '#') continue; insert(hao[x][y], hao[i][j]); } } for(int i = 1;i <= cnt2;++ i) if(lk2[i] == -1) dfs2(i); int flag = 0; for(int i = 1;i <= n;++ i) for(int j = 1;j <= m;++ j) if(s[i][j] == '#') continue; else if((i + j) & 1 && vis1[hao[i][j]]) { if(!flag) printf("WIN\n"), flag = 1; printf("%d %d\n", i, j); } else if(!((i + j) & 1) && vis2[hao[i][j]]) { if(!flag) printf("WIN\n"), flag = 1; printf("%d %d\n", i, j); } if(!flag) printf("LOSE"); return 0;}

转载于:https://www.cnblogs.com/huibixiaoxing/p/8425802.html

你可能感兴趣的文章

《java编程思想》读书笔记（一）开篇&第五章(1)