HDU 5113 Black And White（2014ACM/ICPC北京赛区B）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5113
看到题目的时候第一反应是没有思路，并不知道如何将k种颜色放到N*M的棋盘里，后来观察到数据范围只有（0<n,m<5），于是反应过来这道题目直接暴力搜索可以解决。不过最后并没有时间动手去敲这道题，而且赛后看过题解后发现思路有些小问题，我想在搜索过程中一次放完一种颜色，这实际上是类似于构造的做法，如果真的按照这个思路走那么最后也许会推翻搜索算法（因为放置方案构造清楚后搜索过程显然不必要）尝试进行构造解决，那么我们可能就会陷入对构造方案的繁琐讨论中，风险很大。这种现状反映了我搜索的方案设计的能力不足的问题，实际上一直都很怕写搜索题，思路并不能很清晰。这场就老老实实补题。
设dfs（i，j）表示在第（i，j）个格子内放置颜色，就变成了裸深搜题目，需要判断是否存在方案，显然对于某种颜色i，如果cnt[i]>(n*m+1)/2,那么不管怎么放都一定会存在相邻，此时不存在放置方案；
对于剩下的情况，深搜解决即可。注意姿势不好可能会T掉。具体细节请参阅代码。

【参考代码】

#include<cstdio>
#include<iostream>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,k,cas=1;
int board[10][10];
int ok;
struct color
{
int id,cnt;
}c[100];
int cmp( color A, color B){ return A.cnt>B.cnt; }
void print()
{
printf("Case #%d:nYESn",cas++);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if( j==m)printf("%dn",board[i][j]);
else printf("%d ",board[i][j]);
}
void dfs( int x, int y )
{
for(int i=1;i<=k;i++)if(ok==-1)return;
//ok设成了bool量，所以完全没用到，T在了这里。
else if(c[i].cnt)
{
if(board[x-1][y]!=c[i].id && board[x][y-1]!=c[i].id)
{
c[i].cnt--;
board[x][y]=c[i].id;
if(x==n && y==m
&& ok!=-1){ ok=-1;
print(); return; }
if(y==m)dfs(x+1,1);
else dfs(x,y+1);
c[i].cnt++;
//
board[x][y]=0;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&c[i].cnt);
c[i].id=i;
}
sort(c+1,c+k+1,cmp);
if(c[1].cnt>(n*m+1)/2){
printf("Case #%d:nNOn",cas++); continue; }
//memset(board,0,sizeof(board));
ok=0;
dfs(1,1);
}
return 0;
}

最后

以上就是认真板凳为你收集整理的HDU 5113 Black And White（2014ACM/ICPC北京赛区B）的全部内容，希望文章能够帮你解决HDU 5113 Black And White（2014ACM/ICPC北京赛区B）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。