首页 > 专题系列 > Java解POJ > POJ 2488 A Knight’s Journey [解题报告] Java
2013
11-11

POJ 2488 A Knight’s Journey [解题报告] Java

A Knight’s Journey

问题描述 :

Background

The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey

around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem

Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

输入:

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

输出:

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.

If no such path exist, you should output impossible on a single line.

样例输入:

3
1 1
2 3
4 3

样例输出:

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4

解题代码:

import java.io.PrintWriter;  
 import java.util.Scanner;  
 import java.util.Stack;  
 public class Main {  
  static class Point{  
   int x ,y;  
   public Point(int x ,int y){  
    this.x = x;  
    this.y = y;  
   }  
  }  

 static int[][] chessboard = new int[27][27];  
  static int num = 1;  
 static int[] DX = {-1,1,-2,2,-2,2,-1,1};  
  static int[] DY = {-2,-2,-1,-1,1,1,2,2};  

  public static void main(String[] args) {  
    Scanner scn = new Scanner(System.in);  
  
   PrintWriter out = new PrintWriter(System.out);  
   int n ,p,q;  
   n = scn.nextInt();  
   int index = 1;  
   while(n-- > 0){  
    p = scn.nextInt();  
    q = scn.nextInt();  
    out.format("Scenario #%d:\n%s\n\n", index++,calute(p,q));  
   }  
   out.flush();  
  }  
  static boolean find;//找到标志  
  private static String calute(int p, int q) {  
   //Queue points = new LinkedList();  
   Stack result = new Stack();  
   num = 1;  
   find = false;  
   int[][] visited = new int[p][q];  
   result.add("A1");  
   visited[0][0] = 1;  
   bfs(p,q,new Point(0,0),result,visited);  
   if(!find){  
    return "impossible";  
   }  
   return getResult(result);  
  }  
  private static String getResult(Stack result) {  
   StringBuffer sbf = new StringBuffer("");  
   for(String str : result){  
    sbf.append(str);  
   }  
   return sbf.toString();  
  }  
  private static void bfs(int p, int q, Point point, Stack result, int[][] visited) {  
   int x = point.x, y = point.y, nx,ny;  
   if(num == (p*q)){  
    find = true;  
   }  
   for(int i = 0; i < 8 && !find; i++){  
    nx = x + DX[i];  
    ny = y + DY[i];  
       
    if((nx <0 || nx >= p) || (ny < 0 || ny >= q)){  
     continue;  
    }  
    //已访问过  
    if(visited[nx][ny] == 1){  
     continue;  
    }  
    result.add((char)('A' + ny) + "" + (nx + 1));  
    visited[nx][ny] = 1;  
    num++;  
    bfs(p,q,new Point(nx,ny),result,visited);  
    if(find){  
     break;  
    }  
    visited[nx][ny] = 0;  
    num--;  
    result.pop();  
       
   }  
  }  
    
 }

  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  4. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  5. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥