hdu 5113 Black And White
题意是说用k重颜色填充n*m的方格，第i种颜色要用ci次，保证ci（i属于1..k）的和为n"m，问是否有可行解，若有，输出任意一种。 第一感觉是dfs.。。而且数据范围还那么小。但是鉴于我上次dfs写成汪的经历....嗯 不过群里有学长说似乎剪枝不太好想？ 我一开始分了四类，o行o列，e行e列，e行o列，o行e列，（o是odd，e是even）然后将c[i]排序，先填大的C[I]，感觉这样应该更容易找到解。交了一发,WA掉了。。发现当k较小的时候，也就是c[i]都相对较大的时候，先填大的C[I]的策略会出现错误。于是我换了下....按c[i]的大小从两边往中间...然后我还发现其实o行o列和e行e列可以归为一类，同理，后两种也可以归为一类。又交，又WA2333333 然后想了好久。。。 发现对于上面说的两类的处理顺序不同会得到不同的结果.......只有一种是对的。于是加了个judge函数判断冲突...如果冲突就换个顺序.....再交，A了。
过程中出现了两个语法上的错误....**一个是=写成了==(从来都是把==写成=。。。) 另一个是无参数的函数依然要写（）。。。。。。
确实不难....的确是我生疏了。
1
2
3 /* ***********************************************
4 Author :111qqz
5 Created Time :2016年02月19日 星期五 16时20分07秒
6 File Name :code/hdu/5113.cpp
7 ************************************************ */
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstring>
12
13 using namespace std;
14
15 int c[100],cc[100];
16 int ans[10][10];
17 int colorid[100];
18 int n,m,k;
19 void look();
20 bool judge();
21
22
23 int main()
24 {
25 int tt;
26 int t;
27 int kk;
28
29 cin>>t;
30 tt=t;
31
32
33 int i,j;
34 int head;
35 int flag;
36 while (t--)
37 { head=1;
38 flag=1;
39 memset(ans,0,sizeof(ans));
40 cin>>n>>m>>k;
41 kk=k;
42 for (i=1;i<=k;i++)
43 cin>>c[i];
44
45 for (i=1;i<=k;i++)
46 colorid[i]=i;
47 for (i=1;i<k;i++)
48 for (j=i+1;j<=k;j++)
49 if (c[i]>c[j])
50 {
51 swap(c[i],c[j]);
52 swap(colorid[i],colorid[j]);
53 }
54 for (i=1;i<=k;i++)
55 cc[i]=c[i];
56
57
58
59 if (c[k]>(n*m+1)/2) { cout<<"Case #"<<tt-t<<":"<<endl;cout<<"NO"<<endl;continue;}
60
61 for (i=1;i<=n;i++)
62 for (j=1;j<=m;j++)
63 if ((i%2+j%2)%2==1)
64 {
65 if (flag%2==1)
66 {
67
68
69 ans[i][j]=colorid[k];
70 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
71
72 c[k]--;
73 if (c[k]==0)
74 {
75 k--;
76 flag++;
77
78 }
79 }
80 else
81 {
82 ans[i][j]=colorid[head];
83
84 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
85 c[head]--;
86 if (c[head]==0)
87 {
88 head++;
89 flag++;
90
91 }
92 }
93 // look();
94 }
95
96
97 for (i=1;i<=n;i++)
98 for (j=1;j<=m;j++)
99 if ((i%2+j%2)%2==0)
100 {
101
102
103 if (flag%2==1)
104 {
105
106
107 ans[i][j]=colorid[k];
108 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
109 c[k]--;
110 if (c[k]==0)
111 {
112 k--;
113 flag++;
114 }
115 }
116 else
117 {
118 ans[i][j]=colorid[head];
119 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
120 c[head]--;
121 if (c[head]==0)
122 {
123 head++;
124 flag++;
125 }
126 }
127 // look();
128 }
129 cout<<"Case #"<<tt-t<<":"<<endl;
130 cout<<"YES"<<endl;
131
132 if (!judge())
133 look();
134 else
135 {
136
137
138 k=kk;
139 head=1;
140 flag=1;
141 for (i=1;i<=k;i++)
142 c[i]=cc[i];
143 memset(ans,0,sizeof(ans));
144
145 for (i=1;i<=n;i++)
146 for (j=1;j<=m;j++)
147 if ((i%2+j%2)%2==0)
148 {
149 if (flag%2==1)
150 {
151 ans[i][j]=colorid[k];
152 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
153
154 c[k]--;
155 if (c[k]==0)
156 {
157 k--;
158 flag++;
159
160 }
161 }
162 else
163 {
164 ans[i][j]=colorid[head];
165
166 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
167 c[head]--;
168 if (c[head]==0)
169 {
170 head++;
171 flag++;
172
173 }
174 }
175 // look();
176 }
177 for (i=1;i<=n;i++)
178 for (j=1;j<=m;j++)
179 if ((i%2+j%2)%2==1)
180 {
181
182
183 if (flag%2==1)
184 {
185
186
187 ans[i][j]=colorid[k];
188 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
189 c[k]--;
190 if (c[k]==0)
191 {
192 k--;
193 flag++;
194 }
195 }
196 else
197 {
198 ans[i][j]=colorid[head];
199 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
200 c[head]--;
201 if (c[head]==0)
202 {
203 head++;
204 flag++;
205 }
206 }
207 // look();
208 }
209 look();
210
211 }
212
213
214
215 }
216 return 0;
217 }
218
219
220 void look()
221 {
222 // cout<<"lookkkkkkkkkkkkkkkkkkkkk"<<endl;
223 int i,j;
224 for (i=1;i<=n;i++)
225 for (j=1;j<=m;j++)
226 if (j!=m)
227 cout<<ans[i][j]<<" ";
228 else cout<<ans[i][j]<<endl;
229
230 }
231 bool judge()
232 {
233 int i,j;
234 for (i=1;i<=n;i++)
235 for (j=1;j<m;j++)
236 if (ans[i][j]==ans[i][j+1])
237 return true;
238 for (i=1;i<n;i++)
239 for (j=1;j<=m;j++)
240 if (ans[i][j]==ans[i+1][j])
241 return true;
242 return false;
243 }
244
245
246