[题解]Codeforces Round #254 (Div. 2) A

链接：http://codeforces.com/contest/445/problem/A

描述：一个n*m的棋盘，有一些格子不能放棋子。现在把黑白棋子往上放，要求放满且相邻格子的棋子颜色不同。输出一种可行解。

思路：脑筋急转弯。。。

下过国际象棋的都知道，棋盘本身可以染色成为黑白相间的格子，毁掉其中的格子后也不会影响其2-SAT的性质。直接输出再加一个判断当前格子是否能放棋子就可以了。

我的实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define MaxN 120
 6 char str[MaxN][MaxN];
 7 int n,m;
 8 int main()
 9 {
10     int i,j,cur;
11     scanf("%d%d",&n,&m);
12     for(i=1;i<=n;++i)
13         scanf("%s",str[i]+1);
14     cur=0;
15     for(i=1;i<=n;++i)
16     {
17         for(j=1;j<=m;++j)
18         {
19             cur=(cur+1)%2;
20             if(str[i][j]=='-')
21                 printf("-");
22             else if(cur)
23                 printf("B");
24             else
25                 printf("W");
26         }
27         if(m%2==0)
28             cur=(cur+1)%2;
29         printf("
");
30     }
31     return 0;
32 }

View Code

效率：

然后要说的是，zyy太蠢了，一看完题目没多想就觉得是经典的2-SAT问题，然后就写啊写，结果WA了。。。。zyy觉得最多是个时间超限或者内存超限，怎么可能会WA掉！！！容后查错吧，先挖坑~~

我的实现（经典2-SAT写法，WA）：

  1 #include <iostream>
  2 #include <cstdio>
  3 using namespace std;
  4 #define MaxN 20020
  5 #define MaxM 160020
  6 #define Maxn 120
  7 int n,m,N;
  8 struct node
  9 {
 10     int v;
 11     node *next;
 12 };
 13 node edge[MaxM];
 14 node *cnt=&edge[0];
 15 node *adj[MaxN];
 16 node edge2[MaxM];
 17 node *cnt2=&edge2[0];
 18 node *adj2[MaxN];
 19 int dfn[MaxN],low[MaxN],dcnt;
 20 int stack[MaxN],top;
 21 int Belong[MaxN],Num[MaxN],opp[MaxN],scc;
 22 int In[MaxN],q[MaxN],col[MaxN];
 23 bool Instack[MaxN],ans[MaxN];
 24 char str[Maxn][Maxn];
 25 inline void Addedge(int u,int v)
 26 {
 27     node *p=++cnt;
 28     p->v=v;
 29     p->next=adj[u];
 30     adj[u]=p;
 31 }
 32 inline void Addedge2(int u,int v)
 33 {
 34     node *p=++cnt2;
 35     p->v=v;
 36     p->next=adj2[u];
 37     adj2[u]=p;
 38 }
 39 void Read()
 40 {
 41     scanf("%d%d",&n,&m);
 42     N=n*m;
 43     int i,j;
 44     for(i=1;i<=n;++i)
 45     {
 46         scanf("%s",str[i]+1);
 47         for(j=1;j<=m;++j)
 48             if(str[i][j]=='.')
 49             {
 50                 if(i>1&&str[i-1][j]=='.')
 51                 {
 52                     Addedge((i-1)*m+j,(i-2)*m+j+N);
 53                     Addedge((i-1)*m+j+N,(i-2)*m+j);
 54                 }
 55                 if(j>1&&str[i][j-1]=='.')
 56                 {
 57                     Addedge((i-1)*m+j,(i-1)*m+j-1+N);
 58                     Addedge((i-1)*m+j+N,(i-1)*m+j-1);
 59                 }
 60             }
 61     }
 62 }
 63 void Tarjan(int u)
 64 {
 65     int v;
 66     dfn[u]=low[u]=++dcnt;
 67     stack[++top]=u;
 68     Instack[u]=true;
 69     for(node *p=adj[u];p;p=p->next)
 70     {
 71         v=p->v;
 72         if(!dfn[v])
 73         {
 74             Tarjan(v);
 75             low[u]=min(low[u],low[v]);
 76         }
 77         else if(Instack[v])
 78             low[u]=min(low[u],dfn[v]);
 79     }
 80     if(dfn[u]==low[u])
 81     {
 82         scc++;
 83         do
 84         {
 85             v=stack[top];
 86             top--;
 87             Instack[v]=false;
 88             Belong[v]=scc;
 89             Num[scc]++;
 90         }while(v!=u);
 91     }
 92 }
 93 bool Work()
 94 {
 95     int i;
 96     for(i=1;i<=N*2;i++)
 97         if(!dfn[i])
 98             Tarjan(i);
 99     for(i=1;i<=N;++i)
100     {
101         if(Belong[i]==Belong[i+N])
102             return false;
103         opp[Belong[i]]=Belong[i+N];
104         opp[Belong[i+N]]=Belong[i];
105     }
106     int u,v;
107     for(i=1;i<=N*2;i++)
108         for(node *p=adj[i];p;p=p->next)
109         {
110             v=p->v;
111             if(Belong[i]!=Belong[v])
112             {
113                 Addedge2(Belong[v],Belong[i]);
114                 In[Belong[i]]++;
115             }
116         }
117     int l=0,r=0;
118     for(i=1;i<=scc;i++)
119         if(!In[i])
120         {
121             q[r]=i;
122             r++;
123         }
124     while(l<r)
125     {
126         u=q[l];
127         l++;
128         if(!col[u])
129         {
130             col[u]=1;
131             col[opp[u]]=-1;
132         }
133         for(node *p=adj2[u];p;p=p->next)
134         {
135             v=p->v;
136             In[v]--;
137             if(!In[v])
138             {
139                 q[r]=v;
140                 r++;
141             }
142         }
143     }
144     for(i=1;i<=N*2;++i)
145         if(col[Belong[i]]==1)
146             ans[i]=true;
147     return true;
148 }
149 void Print()
150 {
151     if(Work())
152     {
153         int i,j;
154         for(i=1;i<=n;++i)
155         {
156             for(j=1;j<=m;++j)
157             {
158                 if(str[i][j]=='-')
159                     printf("-");
160                 else if(ans[(i-1)*m+j])
161                     printf("B");
162                 else
163                     printf("W");
164             }
165             printf("
");
166         }
167     }
168     else
169         printf("NIE
");
170 }
171 int main()
172 {
173     Read();
174     Print();
175     return 0;
176 }

View Code

欢迎大神指点！！