[JSOI2009]游戏Game

Posted on by

[JSOI2009]游戏Game

Time Limit:10000MS  Memory Limit:165536K
Total Submit:21 Accepted:12
Case Time Limit:1000MS

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
这题好那个啥囧。。。2个月前见到此题毫无思路。。。
然后上个星期突然有一点思路了。。
然后又考虑了N久。。。
（其实是看到了一道数学题，就是（2n+1）*(2n+1)的正方形上求证放的人有必胜策略，这个题目随便放在一个点上，然后吧其它的点按多米诺骨牌配对，然后每次别人走到一个点上我就到配对的那个点上。。。肯定赢。。。）
然后接着想。。那么这个是不是也跟最大匹配有关系呢。。。
想了很久秃然明白了囧。。。
如果一个点一定在最大匹配里。。。
所以从这点出发的交替路肯定只能到达匹配中的点。。
那么每次我都肯定可以顺着匹配边走。。。别人就被我搞死了。。。
如果一个点可以不在最大匹配里。。
那么在那个图里面。。。对方每次顺着匹配边走。。我就被搞死了。。。
所以只需要知道每个点是否可以不在最大匹配里。。。
一开始我直接暴力。。TLE。。
后来发现可以不在的点其实就是当前从vs可达的之类的。。。
就可以A了。。速度爆慢囧。。
Code：

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define tr(e,x) for(vector<int>::iterator e=x.begin();e!=x.end();e++)
#define All(x) x.begin(),x.end()
#define pb push_back
#define OK puts("OK")
const int inf=~0U>>1,maxn=100,maxv=maxn*maxn+10;
using namespace std;
struct Edge
{
int t,c;
Edge*next,*op;
Edge(int _t,int _c,Edge*_n):
t(_t),c(_c),next(_n){}
}*E[maxv]={};
void AddEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
int n,m,v,vs,vt;
bool M[maxn][maxn];
void BuildGraph()
{
v=n*m;vs=v++;vt=v++;
rep(i,n)rep(j,m)
if(M[i][j])
if((i+j)&1)
{
#define A(i,j) ((i)*m+(j))
#define build(ii,jj)
if(M[ii][jj])
AddEdge(A(i,j),A(ii,jj),1)
AddEdge(vs,A(i,j),1);
if(i)build(i-1,j);
if(j)build(i,j-1);
if(i+1<n)build(i+1,j);
if(j+1<m)build(i,j+1);
#undef build
}
else
{
AddEdge(A(i,j),vt,1);
#undef A
}
}
int Vis[maxv]={},flag=0;
int dfs(int x,int m)
{
if(x==vt)return m;
Vis[x]=flag;
for(Edge*e=E[x];e;e=e->next)if(e->c&&Vis[e->t]!=flag)
{
int d=dfs(e->t,min(m,e->c));
if(d) return e->c-=d,e->op->c+=d,d;
}
return 0;
}
void Init()
{
scanf("%d%d",&n,&m);char c;
rep(i,n)
{
scanf(" ");
rep(j,m)
c=getchar(),M[i][j]=c==’.';
}
}
bool dead[maxv]={},type;
bool Type(int v)
{
return (v%m+v/m)&1;
}
int C;
void dfs(int x)
{
Vis[x]=flag;
if(Type(x)==type)
dead[x]=true;
for(Edge*e=E[x];e;e=e->next)
if(e->c==type&&Vis[e->t]!=flag)
dfs(e->t);
}
void Solve()
{
++flag;int Max=0;
while(int d=dfs(vs,inf))++flag,Max+=d;
++flag;
type=1;
dfs(vs);dead[vs]=false;
++flag;
type=0;
dfs(vt);dead[vt]=false;
bool has=false;
rep(i,v)if(dead[i]){has=true;break;}
if(has)
{
puts("WIN");
rep(i,v)if(dead[i])
{
int x=i/m,y=i%m;
printf("%d %dn",x+1,y+1);
}
}
else
{
puts("LOSE");
}
}
int main()
{
//freopen("in","r",stdin);
Init();
BuildGraph();
Solve();
}

116 thoughts on “[JSOI2009]游戏Game”

  10. we prefer to honor many other web web sites on the net, even when they arent linked to us, by linking to them. Below are some webpages worth checking out

    Reply

  36. we like to honor lots of other online websites on the net, even when they arent linked to us, by linking to them. Beneath are some webpages really worth checking out

    Reply

  39. we like to honor quite a few other world wide web internet sites on the web, even when they arent linked to us, by linking to them. Under are some webpages worth checking out

    Reply

  49. we like to honor many other web web-sites around the internet, even though they arent linked to us, by linking to them. Under are some webpages really worth checking out

    Reply

Leave a Reply to 中国脑筋 Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>