Black And White

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 194 Accepted Submission(s): 50
Special Judge

Problem Description In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.
― Wikipedia, the free encyclopedia

In this problem, you have to solve the 4-color problem. Hey, I’m just joking.

You are asked to solve a similar problem:

Color an N × M chessboard with K colors numbered from 1 to K such that no two adjacent cells have the same color (two cells are adjacent if they share an edge). The i-th color should be used in exactly c _i cells.

Matt hopes you can tell him a possible coloring.
Input The first line contains only one integer T (1 ≤ T ≤ 5000), which indicates the number of test cases.

For each test case, the first line contains three integers: N, M, K (0 < N, M ≤ 5, 0 < K ≤ N × M ).

The second line contains K integers c _i (c _i > 0), denoting the number of cells where the i-th color should be used.

It’s guaranteed that c ₁ + c ₂ + ? ? ? + c _K = N × M .

Output For each test case, the first line contains “Case #x:”, where x is the case number (starting from 1).

In the second line, output “NO” if there is no coloring satisfying the requirements. Otherwise, output “YES” in one line. Each of the following N lines contains M numbers seperated by single whitespace, denoting the color of the cells.

If there are multiple solutions, output any of them.
Sample Input

Sample Output

Case #1:
NO
Case #2:
YES
4 3 4
2 1 2
4 3 4
Case #3:
YES
1 2 3
2 3 1
Case #4:
YES
1 2
2 3
3 1

Source 2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交）

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int n,m,k; int mp[6][6]; struct CC { int num,color; }c[30]; int color[30]; int ccc[30]; bool cmp(CC a,CC b) { return a.num
      
       =0&&x
       
        =0&&y
        
         (cnt+1)/2) return false; } for(int i=0;i
         
          =m) {ny=0; nx++;} dfs(nx,ny,cnt-1); if(flag==true) return true; ccc[color[i]]++; mp[x][y]=0; vis[i]=false; } } return false; } int main() { int T_T,cas=1; scanf("%d",&T_T); while(T_T--) { memset(mp,0,sizeof(mp)); scanf("%d%d%d",&n,&m,&k); for(int i=0;i
          
           (((n+1)/2)*((m+1)/2)+(n/2)*(m/2))) { puts("NO"); continue; } int pos=0; for(int i=0;i

HDOJ 5113 Black And White DFS+剪枝

Black And White