首页 > 专题系列 > Java解POJ > POJ 3194 Equidivisions [解题报告] Java
2013
11-12

POJ 3194 Equidivisions [解题报告] Java

Equidivisions

问题描述 :

An equidivision of an n × n square array of cells is a partition of the n2 cells in the array in exactly n sets, each one with n contiguous cells. Two cells are contiguous when they have a common side.

A good equidivision is composed of contiguous regions. The figures show a good and a wrong equidivision for a 5 × 5 square:

Note that in the second example the cells labeled with 4 describe three non-contiguous regions and cells labeled with 5 describe two non-contiguous regions. You must write a program that evaluates if an equidivision of the cells in a square array is good or not.

输入:

It is understood that a cell in an n × n square array is denoted by a pair (i, j), with 1 ≤ i, jn. The input file contains several test cases. Each test case begins with a line indicating n, 0 < n < 100, the side of the square array to be partitioned. Next, there are n − 1 lines, each one corresponding to one partition of the cells of the square, with some non-negative integer numbers. Consecutive integers in a line are separated with a single blank character. A line of the form

a1a2a3a4

means that cells denoted with the pairs (a1, a2), (a3, a4), … belong to one of the areas in the partition. The last area in the partition is defined by those cells not mentioned in the n − 1 given lines. If a case begins with n = 0 it means that there are no more cases to analyze.

输出:

For each test case good must be printed if the equidivision is good, in other case, wrong must be printed. The answers for the different cases must preserve the order of the input.

样例输入:

2
1 2 2 1
5
1 1 1 2 1 3 3 2 2 2
2 1 4 2 4 1 5 1 3 1
4 5 5 2 5 3 5 5 5 4
2 5 3 4 3 5 4 3 4 4
5
1 1 1 2 1 3 3 2 2 2
2 1 3 1 4 1 5 1 4 2
4 5 5 2 5 3 5 5 5 4
2 4 1 4 3 5 4 3 4 4
0

样例输出:

wrong
good
wrong

解题代码:

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 static int p[][]=new int[105][105];
 static int q[][]=new int[101][101];
 static int n,cnt;


static void dfs(int i,int j)
{
  if(i>n||j>n||i< 1||j< 1) return;
  q[i][j]=cnt;
  if(q[i][j+1]==0&&p[i][j]==p[i][j+1]) dfs(i,j+1);
  if(q[i][j-1]==0&&p[i][j]==p[i][j-1]) dfs(i,j-1);
  if(q[i+1][j]==0&&p[i][j]==p[i+1][j]) dfs(i+1,j);
  if(q[i-1][j]==0&&p[i][j]==p[i-1][j]) dfs(i-1,j);
}

 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
	
 int i,j,u,v;

 while(sc.hasNext())
 {
   n=sc.nextInt();
  if(n==0) break;
  for(i=0;i< p.length;i++){
  Arrays.fill(p[i],0);
 }
 for(i=0;i< q.length;i++){
     Arrays.fill(q[i],0);
 }
       
for(i=0;i< n-1;i++)
{
  for(j=0;j< n;j++)
  {
	u=sc.nextInt();
      v=sc.nextInt();
      p[u][v]=i+1;
   }
 }
 cnt=1;
 for(i=1;i<=n;i++)
 {
   for(j=1;j<=n;j++)
   {
	if(q[i][j]!=0) continue;
	dfs(i,j);
	cnt++;
   }
  }
  cnt--;
  if(cnt>n) System.out.println("wrong");
  else System.out.println("good");
  }
 }
}

  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?