首页 > 专题系列 > Java解POJ > POJ 2893 M × N Puzzle [解题报告] Java
2013
11-12

POJ 2893 M × N Puzzle [解题报告] Java

M × N Puzzle

问题描述 :

The Eight Puzzle, among other sliding-tile puzzles, is one of the famous problems in artificial intelligence. Along with chess, tic-tac-toe and backgammon, it has been used to study search algorithms.

The Eight Puzzle can be generalized into an M × N Puzzle where at least one of M and N is odd. The puzzle is constructed with MN − 1 sliding tiles with each a number from 1 to MN − 1 on it packed into a M by N frame with one tile missing. For example, with M = 4 and N = 3, a puzzle may look like:

1 6 2
4 0 3
7 5 9
10 8 11

Let’s call missing tile 0. The only legal operation is to exchange 0 and the tile with which it shares an edge. The goal of the puzzle is to find a sequence of legal operations that makes it look like:

1 2 3
4 5 6
7 8 9
10 11 0

The following steps solve the puzzle given above.

START

1 6 2
4 0 3
7 5 9
10 8 11

DOWN

1 0 2
4 6 3
7 5 9
10 8 11
LEFT
1 2 0
4 6 3
7 5 9
10 8 11

UP

1 2 3
4 6 0
7 5 9
10 8 11

RIGHT

1 2 3
4 0 6
7 5 9
10 8 11

UP

1 2 3
4 5 6
7 0 9
10 8 11
UP
1 2 3
4 5 6
7 8 9
10 0 11

LEFT

1 2 3
4 5 6
7 8 9
10 11 0

GOAL

Given an M × N puzzle, you are to determine whether it can be solved.

输入:

The input consists of multiple test cases. Each test case starts with a line containing M and N (2 M, N ≤ 999). This line is followed by M lines containing N numbers each describing an M × N puzzle.

The input ends with a pair of zeroes which should not be processed.

输出:

Output one line for each test case containing a single word YES if the puzzle can be solved and NO otherwise.

样例输入:

3 3
1 0 3
4 2 5
7 8 6
4 3
1 2 5
4 6 9
11 8 10
3 7 0
0 0

样例输出:

YES
NO

解题代码:

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

public class Main {
 static final int M = 1000+2;
 static final int N = 1000000+10;
 static int sort[] = new int[N],map[][] = new int[M][M];
 public static void main(String []args) throws Exception{
		
  int i,j,n,m,top,a,b;
  int num[] = new int[N];
		
  StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  while(true){
	n = Get_Num(cin);
	m = Get_Num(cin);
	if(n==0 && m==0) break;
	for(i=top=0;i< n;++i)
	  for(j=0;j< m;++j){
		map[i][j] = Get_Num(cin);
	  }
	if(m%2==1){
		for(i=0;i< n;++i) 
		 for(j=0;j< m;++j) if(map[i][j]>0)
			num[top++] = map[i][j];
	}else{
		for(i=0;i< m;++i)
		  for(j=0;j< n;++j) if(map[j][i]>0)
			num[top++] = map[j][i];
	}
	a = merge(num,0,top-1);
	if(m%2==1){
		if(a%2==0) System.out.println("YES");
		else System.out.println("NO");
	}
	else{
		for(i=top=0;i< n;++i)
		  for(j=0;j< m;++j)
			map[i][j] = ++top;
		map[n-1][m-1] = 0;
		for(i=top=0;i< m;++i) 
		 for(j=0;j< n;++j) if(map[j][i]>0)
			num[top++] = map[j][i];
		b = merge(num,0,top-1);
		if(a%2==b%2) System.out.println("YES");
		else System.out.println("NO");
	}
    }
		
  }

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


  public static int merge(int num[],int left,int right){
		
	if(left==right){
		sort[left] = num[left];
		return 0;
	}
	int mid,i,j,ans=0,top=0;
	mid = (left+right)/2;
	ans = merge(num,left,mid)%2;
	ans += merge(num,mid+1,right)%2;
	
	i = left ; j = mid+1;
	while(i<=mid && j<=right){
		if(num[i]>num[j]){
			ans += (mid-i+1)%2;
			sort[top++] = num[j++];
		}
		else{
			sort[top++] = num[i++];
		}
	}
	while(i<=mid)
		sort[top++] = num[i++];
	while(j<=right)
		sort[top++] = num[j++];
	for(i=left;i<=right;++i)
		num[i] = sort[i-left];
	
	return ans;
  }
}

  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  3. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;