题意是说用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了。
过程中出现了两个语法上的错误....一个是=写成了==(从来都是把==写成=。。。)
另一个是无参数的函数依然要写()。。。。。。
确实不难....的确是我生疏了。
C++语言: 高亮代码由发芽网提供
001 #include <iostream>
002 #include <algorithm>
003 #include <cstring>
004
005 using namespace std;
006
007 int c[100],cc[100];
008 int ans[10][10];
009 int colorid[100];
010 int n,m,k;
011 void look();
012 bool judge();
013
014
015 int main()
016 {
017 int tt;
018 int t;
019 int kk;
020
021 cin>>t;
022 tt=t;
023
024
025 int i,j;
026 int head;
027 int flag;
028 while (t--)
029 { head=1;
030 flag=1;
031 memset(ans,0,sizeof(ans));
032 cin>>n>>m>>k;
033 kk=k;
034 for (i=1;i<=k;i++)
035 cin>>c[i];
036
037 for (i=1;i<=k;i++)
038 colorid[i]=i;
039 for (i=1;i<k;i++)
040 for (j=i+1;j<=k;j++)
041 if (c[i]>c[j])
042 {
043 swap(c[i],c[j]);
044 swap(colorid[i],colorid[j]);
045 }
046 for (i=1;i<=k;i++)
047 cc[i]=c[i];
048
049
050
051 if (c[k]>(n*m+1)/2) { cout<<"Case #"<<tt-t<<":"<<endl;cout<<"NO"<<endl;continue;}
052
053 for (i=1;i<=n;i++)
054 for (j=1;j<=m;j++)
055 if ((i%2+j%2)%2==1)
056 {
057 if (flag%2==1)
058 {
059
060
061 ans[i][j]=colorid[k];
062 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
063
064 c[k]--;
065 if (c[k]==0)
066 {
067 k--;
068 flag++;
069
070 }
071 }
072 else
073 {
074 ans[i][j]=colorid[head];
075
076 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
077 c[head]--;
078 if (c[head]==0)
079 {
080 head++;
081 flag++;
082
083 }
084 }
085 // look();
086 }
087
088
089 for (i=1;i<=n;i++)
090 for (j=1;j<=m;j++)
091 if ((i%2+j%2)%2==0)
092 {
093
094
095 if (flag%2==1)
096 {
097
098
099 ans[i][j]=colorid[k];
100 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
101 c[k]--;
102 if (c[k]==0)
103 {
104 k--;
105 flag++;
106 }
107 }
108 else
109 {
110 ans[i][j]=colorid[head];
111 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
112 c[head]--;
113 if (c[head]==0)
114 {
115 head++;
116 flag++;
117 }
118 }
119 // look();
120 }
121 cout<<"Case #"<<tt-t<<":"<<endl;
122 cout<<"YES"<<endl;
123
124 if (!judge())
125 look();
126 else
127 {
128
129
130 k=kk;
131 head=1;
132 flag=1;
133 for (i=1;i<=k;i++)
134 c[i]=cc[i];
135 memset(ans,0,sizeof(ans));
136
137 for (i=1;i<=n;i++)
138 for (j=1;j<=m;j++)
139 if ((i%2+j%2)%2==0)
140 {
141 if (flag%2==1)
142 {
143 ans[i][j]=colorid[k];
144 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
145
146 c[k]--;
147 if (c[k]==0)
148 {
149 k--;
150 flag++;
151
152 }
153 }
154 else
155 {
156 ans[i][j]=colorid[head];
157
158 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
159 c[head]--;
160 if (c[head]==0)
161 {
162 head++;
163 flag++;
164
165 }
166 }
167 // look();
168 }
169 for (i=1;i<=n;i++)
170 for (j=1;j<=m;j++)
171 if ((i%2+j%2)%2==1)
172 {
173
174
175 if (flag%2==1)
176 {
177
178
179 ans[i][j]=colorid[k];
180 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
181 c[k]--;
182 if (c[k]==0)
183 {
184 k--;
185 flag++;
186 }
187 }
188 else
189 {
190 ans[i][j]=colorid[head];
191 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
192 c[head]--;
193 if (c[head]==0)
194 {
195 head++;
196 flag++;
197 }
198 }
199 // look();
200 }
201 look();
202
203 }
204
205
206
207 }
208 return 0;
209 }
210
211
212 void look()
213 {
214 // cout<<"lookkkkkkkkkkkkkkkkkkkkk"<<endl;
215 int i,j;
216 for (i=1;i<=n;i++)
217 for (j=1;j<=m;j++)
218 if (j!=m)
219 cout<<ans[i][j]<<" ";
220 else cout<<ans[i][j]<<endl;
221
222 }
223 bool judge()
224 {
225 int i,j;
226 for (i=1;i<=n;i++)
227 for (j=1;j<m;j++)
228 if (ans[i][j]==ans[i][j+1])
229 return true;
230 for (i=1;i<n;i++)
231 for (j=1;j<=m;j++)
232 if (ans[i][j]==ans[i+1][j])
233 return true;
234 return false;
235 }
002 #include <algorithm>
003 #include <cstring>
004
005 using namespace std;
006
007 int c[100],cc[100];
008 int ans[10][10];
009 int colorid[100];
010 int n,m,k;
011 void look();
012 bool judge();
013
014
015 int main()
016 {
017 int tt;
018 int t;
019 int kk;
020
021 cin>>t;
022 tt=t;
023
024
025 int i,j;
026 int head;
027 int flag;
028 while (t--)
029 { head=1;
030 flag=1;
031 memset(ans,0,sizeof(ans));
032 cin>>n>>m>>k;
033 kk=k;
034 for (i=1;i<=k;i++)
035 cin>>c[i];
036
037 for (i=1;i<=k;i++)
038 colorid[i]=i;
039 for (i=1;i<k;i++)
040 for (j=i+1;j<=k;j++)
041 if (c[i]>c[j])
042 {
043 swap(c[i],c[j]);
044 swap(colorid[i],colorid[j]);
045 }
046 for (i=1;i<=k;i++)
047 cc[i]=c[i];
048
049
050
051 if (c[k]>(n*m+1)/2) { cout<<"Case #"<<tt-t<<":"<<endl;cout<<"NO"<<endl;continue;}
052
053 for (i=1;i<=n;i++)
054 for (j=1;j<=m;j++)
055 if ((i%2+j%2)%2==1)
056 {
057 if (flag%2==1)
058 {
059
060
061 ans[i][j]=colorid[k];
062 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
063
064 c[k]--;
065 if (c[k]==0)
066 {
067 k--;
068 flag++;
069
070 }
071 }
072 else
073 {
074 ans[i][j]=colorid[head];
075
076 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
077 c[head]--;
078 if (c[head]==0)
079 {
080 head++;
081 flag++;
082
083 }
084 }
085 // look();
086 }
087
088
089 for (i=1;i<=n;i++)
090 for (j=1;j<=m;j++)
091 if ((i%2+j%2)%2==0)
092 {
093
094
095 if (flag%2==1)
096 {
097
098
099 ans[i][j]=colorid[k];
100 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
101 c[k]--;
102 if (c[k]==0)
103 {
104 k--;
105 flag++;
106 }
107 }
108 else
109 {
110 ans[i][j]=colorid[head];
111 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
112 c[head]--;
113 if (c[head]==0)
114 {
115 head++;
116 flag++;
117 }
118 }
119 // look();
120 }
121 cout<<"Case #"<<tt-t<<":"<<endl;
122 cout<<"YES"<<endl;
123
124 if (!judge())
125 look();
126 else
127 {
128
129
130 k=kk;
131 head=1;
132 flag=1;
133 for (i=1;i<=k;i++)
134 c[i]=cc[i];
135 memset(ans,0,sizeof(ans));
136
137 for (i=1;i<=n;i++)
138 for (j=1;j<=m;j++)
139 if ((i%2+j%2)%2==0)
140 {
141 if (flag%2==1)
142 {
143 ans[i][j]=colorid[k];
144 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
145
146 c[k]--;
147 if (c[k]==0)
148 {
149 k--;
150 flag++;
151
152 }
153 }
154 else
155 {
156 ans[i][j]=colorid[head];
157
158 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
159 c[head]--;
160 if (c[head]==0)
161 {
162 head++;
163 flag++;
164
165 }
166 }
167 // look();
168 }
169 for (i=1;i<=n;i++)
170 for (j=1;j<=m;j++)
171 if ((i%2+j%2)%2==1)
172 {
173
174
175 if (flag%2==1)
176 {
177
178
179 ans[i][j]=colorid[k];
180 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[k]<<endl;
181 c[k]--;
182 if (c[k]==0)
183 {
184 k--;
185 flag++;
186 }
187 }
188 else
189 {
190 ans[i][j]=colorid[head];
191 // cout<<"i:"<<i<<"j:"<<j<<" "<<colorid[head]<<endl;
192 c[head]--;
193 if (c[head]==0)
194 {
195 head++;
196 flag++;
197 }
198 }
199 // look();
200 }
201 look();
202
203 }
204
205
206
207 }
208 return 0;
209 }
210
211
212 void look()
213 {
214 // cout<<"lookkkkkkkkkkkkkkkkkkkkk"<<endl;
215 int i,j;
216 for (i=1;i<=n;i++)
217 for (j=1;j<=m;j++)
218 if (j!=m)
219 cout<<ans[i][j]<<" ";
220 else cout<<ans[i][j]<<endl;
221
222 }
223 bool judge()
224 {
225 int i,j;
226 for (i=1;i<=n;i++)
227 for (j=1;j<m;j++)
228 if (ans[i][j]==ans[i][j+1])
229 return true;
230 for (i=1;i<n;i++)
231 for (j=1;j<=m;j++)
232 if (ans[i][j]==ans[i+1][j])
233 return true;
234 return false;
235 }