首页 > 专题系列 > Java解POJ > POJ 2446 Chessboard [解题报告] Java
2013
11-11

POJ 2446 Chessboard [解题报告] Java

Chessboard

问题描述 :

Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of cards with size 1 * 2 to cover the board. However, she thinks it too easy to bob, so she makes some holes on the board (as shown in the figure below).



We call a grid, which doesn’t contain a hole, a normal grid. Bob has to follow the rules below:

1. Any normal grid should be covered with exactly one card.

2. One card should cover exactly 2 normal adjacent grids.

Some examples are given in the figures below:



A VALID solution.




An invalid solution, because the hole of red color is covered with a card.




An invalid solution, because there exists a grid, which is not covered.


Your task is to help Bob to decide whether or not the chessboard can be covered according to the rules above.

输入:

There are 3 integers in the first line: m, n, k (0 < m, n <= 32, 0 <= K < m * n), the number of rows, column and holes. In the next k lines, there is a pair of integers (x, y) in each line, which represents a hole in the y-th row, the x-th column.

输出:

If the board can be covered, output “YES”. Otherwise, output “NO”.

样例输入:

4 3 2
2 1
3 3

样例输出:

YES

温馨提示:



A possible solution for the sample input.

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {
 static final int N = 1030,M = 35;
 static int n,m;
 static int Graph[][] = new int[N][N],map[][] = new int[M][M];
 static int dir[][] = {{0,1},{0,-1},{1,0},{-1,0}};
 static int mat[] = new int[N],tmat[] = new int[N];
 static int hungry_aug(int i,int nt){
	int v,j;
	for(j=0;j< nt;++j){
          if(Graph[i][j]>0 && tmat[j]==0){
		tmat[j] = 1; v = mat[j];mat[j] = i;
		if(v==-1 || hungry_aug(v,nt)>0) return 1;
		mat[j] = v;
	  }
	}
	return 0;
}
 
static int hungry(int nt,int mt){
	int i,j,k=0;
	for(i=0;i< N;++i) mat[i] = -1;
	for(i=0;i< nt;++i){
        for(j=0;j< N;++j) tmat[j] = 0;
		k+=hungry_aug(i,nt);
	}
	return k;
}


 public static void main(String[]args) throws Exception{
		
  int i,j,k,hole,x,y;
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

		
   n = Get_Num(cin);
   m = Get_Num(cin);
   hole = Get_Num(cin);
   init_graph();
   for(i=0;i< hole;++i){
	x = Get_Num(cin)-1;
	y = Get_Num(cin)-1;
	map[y][x] = 1;
   }
   for(i=0;i< n;++i)
    for(j=0;j< m;++j) 
	  if(map[i][j]==0){
	   for(k=0;k< 4;++k)
	    if(can(i+dir[k][0],j+dir[k][1])){
		  x = i*m+j;
		  y = (i+dir[k][0])*m+(j+dir[k][1]);
		  Graph[x][y] = 1;
	     }
      }
  if((n*m-hole)%2==1 || hungry(n*m,n*m)!=(n*m-hole))
	System.out.println("NO");
  else System.out.println("YES");
 }

 static boolean can(int x,int y){
  if(x<0||x>=n||y< 0||y>=m)
	return false;
  if(map[x][y]>0) return false;
	return true;
 }

 static void init_graph(){
   int i,j;
   for(i=0;i< M;++i)
     for(j=0;j< M;++j)
	  map[i][j] = 0;
   for(i=0;i< n*m;++i)
      for(j=0;j< n*m;++j)
	   Graph[i][j] = 0;
 }

  static int Get_Num(StreamTokenizer cin) throws Exception{
	cin.nextToken();
	return (int) cin.nval;
  }
}

  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。