{"id":374,"date":"2010-09-12T11:50:00","date_gmt":"2010-09-12T03:50:00","guid":{"rendered":"http:\/\/localhost\/?p=374"},"modified":"2010-09-12T11:50:00","modified_gmt":"2010-09-12T03:50:00","slug":"jsoi2009_game_game","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=374","title":{"rendered":"[JSOI2009]\u6e38\u620fGame"},"content":{"rendered":"\n

[JSOI2009]\u6e38\u620fGame<\/p>\n

Time Limit:10000MS  Memory Limit:165536K
Total Submit:21 Accepted:12
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

<\/p>\n

Input <\/strong><\/p>\n

\u8f93\u5165\u6570\u636e\u9996\u5148\u8f93\u5165\u4e24\u4e2a\u6574\u6570N,M\uff0c\u8868\u793a\u4e86\u8ff7\u5bab\u7684\u8fb9\u957f\u3002
\u63a5\u4e0b\u6765N\u884c\uff0c\u6bcf\u884cM\u4e2a\u5b57\u7b26\uff0c\u63cf\u8ff0\u4e86\u8ff7\u5bab\u3002 <\/p>\n

Output <\/strong><\/p>\n

\u82e5\u5c0fAA\u80fd\u591f\u8d62\u5f97\u6e38\u620f\uff0c\u5219\u8f93\u51fa\u4e00\u884c"WIN"\uff0c\u7136\u540e\u8f93\u51fa\u6240\u6709\u53ef\u4ee5\u8d62\u5f97\u6e38\u620f\u7684\u8d77\u59cb\u4f4d\u7f6e\uff0c\u6309\u884c\u4f18\u5148\u987a\u5e8f\u8f93\u51fa
\u6bcf\u884c\u4e00\u4e2a,\u5426\u5219\u8f93\u51fa\u4e00\u884c"LOSE"\uff08\u4e0d\u5305\u542b\u5f15\u53f7\uff09\u3002<\/p>\n

Sample Input <\/strong><\/p>\n

3 3
.##
…
#.#<\/p>\n

Sample Output <\/strong><\/p>\n

2 3
3 2<\/p>\n

Hint <\/strong><\/p>\n

\u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c\u67091\u2264n,m\u2264100\u3002
\u5bf9\u4e8e30%\u7684\u6570\u636e\uff0c\u67091\u2264n,m\u22645\u3002<\/p>\n

Source <\/strong><\/p>\n

JSOI2009Day2
\u8fd9\u9898\u597d\u90a3\u4e2a\u5565\u56e7\u3002\u3002\u30022\u4e2a\u6708\u524d\u89c1\u5230\u6b64\u9898\u6beb\u65e0\u601d\u8def\u3002\u3002\u3002
\u7136\u540e\u4e0a\u4e2a\u661f\u671f\u7a81\u7136\u6709\u4e00\u70b9\u601d\u8def\u4e86\u3002\u3002
\u7136\u540e\u53c8\u8003\u8651\u4e86N\u4e45\u3002\u3002\u3002
\uff08\u5176\u5b9e\u662f\u770b\u5230\u4e86\u4e00\u9053\u6570\u5b66\u9898\uff0c\u5c31\u662f\uff082n+1\uff09*(2n+1)\u7684\u6b63\u65b9\u5f62\u4e0a\u6c42\u8bc1\u653e\u7684\u4eba\u6709\u5fc5\u80dc\u7b56\u7565\uff0c\u8fd9\u4e2a\u9898\u76ee\u968f\u4fbf\u653e\u5728\u4e00\u4e2a\u70b9\u4e0a\uff0c\u7136\u540e\u5427\u5176\u5b83\u7684\u70b9\u6309\u591a\u7c73\u8bfa\u9aa8\u724c\u914d\u5bf9\uff0c\u7136\u540e\u6bcf\u6b21\u522b\u4eba\u8d70\u5230\u4e00\u4e2a\u70b9\u4e0a\u6211\u5c31\u5230\u914d\u5bf9\u7684\u90a3\u4e2a\u70b9\u4e0a\u3002\u3002\u3002\u80af\u5b9a\u8d62\u3002\u3002\u3002\uff09
\u7136\u540e\u63a5\u7740\u60f3\u3002\u3002\u90a3\u4e48\u8fd9\u4e2a\u662f\u4e0d\u662f\u4e5f\u8ddf\u6700\u5927\u5339\u914d\u6709\u5173\u7cfb\u5462\u3002\u3002\u3002
\u60f3\u4e86\u5f88\u4e45\u79c3\u7136\u660e\u767d\u4e86\u56e7\u3002\u3002\u3002
\u5982\u679c\u4e00\u4e2a\u70b9\u4e00\u5b9a\u5728\u6700\u5927\u5339\u914d\u91cc\u3002\u3002\u3002
\u6240\u4ee5\u4ece\u8fd9\u70b9\u51fa\u53d1\u7684\u4ea4\u66ff\u8def\u80af\u5b9a\u53ea\u80fd\u5230\u8fbe\u5339\u914d\u4e2d\u7684\u70b9\u3002\u3002
\u90a3\u4e48\u6bcf\u6b21\u6211\u90fd\u80af\u5b9a\u53ef\u4ee5\u987a\u7740\u5339\u914d\u8fb9\u8d70\u3002\u3002\u3002\u522b\u4eba\u5c31\u88ab\u6211\u641e\u6b7b\u4e86\u3002\u3002\u3002
\u5982\u679c\u4e00\u4e2a\u70b9\u53ef\u4ee5\u4e0d\u5728\u6700\u5927\u5339\u914d\u91cc\u3002\u3002
\u90a3\u4e48\u5728\u90a3\u4e2a\u56fe\u91cc\u9762\u3002\u3002\u3002\u5bf9\u65b9\u6bcf\u6b21\u987a\u7740\u5339\u914d\u8fb9\u8d70\u3002\u3002\u6211\u5c31\u88ab\u641e\u6b7b\u4e86\u3002\u3002\u3002
\u6240\u4ee5\u53ea\u9700\u8981\u77e5\u9053\u6bcf\u4e2a\u70b9\u662f\u5426\u53ef\u4ee5\u4e0d\u5728\u6700\u5927\u5339\u914d\u91cc\u3002\u3002\u3002
\u4e00\u5f00\u59cb\u6211\u76f4\u63a5\u66b4\u529b\u3002\u3002TLE\u3002\u3002
\u540e\u6765\u53d1\u73b0\u53ef\u4ee5\u4e0d\u5728\u7684\u70b9\u5176\u5b9e\u5c31\u662f\u5f53\u524d\u4ecevs\u53ef\u8fbe\u7684\u4e4b\u7c7b\u7684\u3002\u3002\u3002
\u5c31\u53ef\u4ee5A\u4e86\u3002\u3002\u901f\u5ea6\u7206\u6162\u56e7\u3002\u3002
Code\uff1a<\/p>\n

#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();
}<\/p>\n","protected":false},"excerpt":{"rendered":"

[JSOI2009]\u6e38\u620fGame Time Limit:10000MS  Memory Limit:165536KTotal Submit:21 Accepted:12 Case Time Limit:1000MS Description Input \u8f93\u5165\u6570\u636e\u9996\u5148\u8f93\u5165\u4e24\u4e2a\u6574\u6570N,M\uff0c\u8868\u793a\u4e86\u8ff7\u5bab\u7684\u8fb9\u957f\u3002 \u63a5\u4e0b\u6765N\u884c\uff0c\u6bcf\u884cM\u4e2a\u5b57\u7b26\uff0c\u63cf\u8ff0\u4e86\u8ff7\u5bab\u3002 Output \u82e5\u5c0fAA\u80fd\u591f\u8d62\u5f97\u6e38\u620f\uff0c\u5219\u8f93\u51fa\u4e00\u884c"WIN"\uff0c\u7136\u540e\u8f93\u51fa\u6240\u6709\u53ef\u4ee5\u8d62\u5f97\u6e38\u620f\u7684\u8d77\u59cb\u4f4d\u7f6e\uff0c\u6309\u884c\u4f18\u5148\u987a\u5e8f\u8f93\u51fa \u6bcf\u884c\u4e00\u4e2a,\u5426\u5219\u8f93\u51fa\u4e00\u884c"LOSE"\uff08\u4e0d\u5305\u542b\u5f15\u53f7\uff09\u3002 Sample Input 3 3.##…#.# Sample Output 2 33 2 Hint \u5bf9\u4e8e100%\u7684\u6570\u636e\uff0c\u67091\u2264n,m\u2264100\u3002 \u5bf9\u4e8e30%\u7684\u6570\u636e\uff0c\u67091\u2264n,m\u22645\u3002 Source JSOI2009Day2\u8fd9\u9898\u597d\u90a3\u4e2a\u5565\u56e7\u3002\u3002\u30022\u4e2a\u6708\u524d\u89c1\u5230\u6b64\u9898\u6beb\u65e0\u601d\u8def\u3002\u3002\u3002\u7136\u540e\u4e0a\u4e2a\u661f\u671f\u7a81\u7136\u6709\u4e00\u70b9\u601d\u8def\u4e86\u3002\u3002\u7136\u540e\u53c8\u8003\u8651\u4e86N\u4e45\u3002\u3002\u3002\uff08\u5176\u5b9e\u662f\u770b\u5230\u4e86\u4e00\u9053\u6570\u5b66\u9898\uff0c\u5c31\u662f\uff082n+1\uff09*(2n+1)\u7684\u6b63\u65b9\u5f62\u4e0a\u6c42\u8bc1\u653e\u7684\u4eba\u6709\u5fc5\u80dc\u7b56\u7565\uff0c\u8fd9\u4e2a\u9898\u76ee\u968f\u4fbf\u653e\u5728\u4e00\u4e2a\u70b9\u4e0a\uff0c\u7136\u540e\u5427\u5176\u5b83\u7684\u70b9\u6309\u591a\u7c73\u8bfa\u9aa8\u724c\u914d\u5bf9\uff0c\u7136\u540e\u6bcf\u6b21\u522b\u4eba\u8d70\u5230\u4e00\u4e2a\u70b9\u4e0a\u6211\u5c31\u5230\u914d\u5bf9\u7684\u90a3\u4e2a\u70b9\u4e0a\u3002\u3002\u3002\u80af\u5b9a\u8d62\u3002\u3002\u3002\uff09\u7136\u540e\u63a5\u7740\u60f3\u3002\u3002\u90a3\u4e48\u8fd9\u4e2a\u662f\u4e0d\u662f\u4e5f\u8ddf\u6700\u5927\u5339\u914d\u6709\u5173\u7cfb\u5462\u3002\u3002\u3002\u60f3\u4e86\u5f88\u4e45\u79c3\u7136\u660e\u767d\u4e86\u56e7\u3002\u3002\u3002\u5982\u679c\u4e00\u4e2a\u70b9\u4e00\u5b9a\u5728\u6700\u5927\u5339\u914d\u91cc\u3002\u3002\u3002\u6240\u4ee5\u4ece\u8fd9\u70b9\u51fa\u53d1\u7684\u4ea4\u66ff\u8def\u80af\u5b9a\u53ea\u80fd\u5230\u8fbe\u5339\u914d\u4e2d\u7684\u70b9\u3002\u3002\u90a3\u4e48\u6bcf\u6b21\u6211\u90fd\u80af\u5b9a\u53ef\u4ee5\u987a\u7740\u5339\u914d\u8fb9\u8d70\u3002\u3002\u3002\u522b\u4eba\u5c31\u88ab\u6211\u641e\u6b7b\u4e86\u3002\u3002\u3002\u5982\u679c\u4e00\u4e2a\u70b9\u53ef\u4ee5\u4e0d\u5728\u6700\u5927\u5339\u914d\u91cc\u3002\u3002\u90a3\u4e48\u5728\u90a3\u4e2a\u56fe\u91cc\u9762\u3002\u3002\u3002\u5bf9\u65b9\u6bcf\u6b21\u987a\u7740\u5339\u914d\u8fb9\u8d70\u3002\u3002\u6211\u5c31\u88ab\u641e\u6b7b\u4e86\u3002\u3002\u3002\u6240\u4ee5\u53ea\u9700\u8981\u77e5\u9053\u6bcf\u4e2a\u70b9\u662f\u5426\u53ef\u4ee5\u4e0d\u5728\u6700\u5927\u5339\u914d\u91cc\u3002\u3002\u3002\u4e00\u5f00\u59cb\u6211\u76f4\u63a5\u66b4\u529b\u3002\u3002TLE\u3002\u3002\u540e\u6765\u53d1\u73b0\u53ef\u4ee5\u4e0d\u5728\u7684\u70b9\u5176\u5b9e\u5c31\u662f\u5f53\u524d\u4ecevs\u53ef\u8fbe\u7684\u4e4b\u7c7b\u7684\u3002\u3002\u3002\u5c31\u53ef\u4ee5A\u4e86\u3002\u3002\u901f\u5ea6\u7206\u6162\u56e7\u3002\u3002Code\uff1a #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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/374"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=374"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/374\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=374"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=374"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=374"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}