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

POJ 3050 Hopscotch [解题报告] Java

Hopscotch

问题描述 :

The cows play the child’s game of hopscotch in a non-traditional way. Instead of a linear set of numbered boxes into which to hop, the cows create a 5×5 rectilinear grid of digits parallel to the x and y axes.

They then adroitly hop onto any digit in the grid and hop forward, backward, right, or left (never diagonally) to another digit in the grid. They hop again (same rules) to a digit (potentially a digit already visited).

With a total of five intra-grid hops, their hops create a six-digit integer (which might have leading zeroes like 000201).

Determine the count of the number of distinct integers that can be created in this manner.

输入:

* Lines 1..5: The grid, five integers per line

输出:

* Line 1: The number of distinct integers that can be constructed

样例输入:

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1

样例输出:

15

温馨提示:

OUTPUT DETAILS:

111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, and 212121 can be constructed. No other values are possible.

解题代码:

import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.HashSet;
 import java.util.Set;

 public class Main {

     static Set set;
     static int[][] a;

     public static void main(String[] args) throws IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         a = new int[5][5];
         String[] s;
         for (int i = 0; i < 5; i++) {
             s = read.readLine().split(" ");
             for (int j = 0; j < 5; j++) {
                 a[i][j] = Integer.parseInt(s[j]);
             }
         }
         set = new HashSet();
         for (int i = 0; i < 5; i++) {
             for (int j = 0; j < 5; j++) {
                 search(0, 0, i, j);
             }
         }
         System.out.println(set.size());
     }

     public static void search(int sum, int dp, int x, int y) {
         if (dp == 6) {
             set.add(sum);
             return;
         }
         if (x - 1 >= 0) {
             search(sum * 10 + a[x - 1][y], dp + 1, x - 1, y);
         }
         if (x + 1 < 5) {
             search(sum * 10 + a[x + 1][y], dp + 1, x + 1, y);
         }
         if (y - 1 >= 0) {
             search(sum * 10 + a[x][y - 1], dp + 1, x, y - 1);
         }
         if (y + 1 < 5) {
             search(sum * 10 + a[x][y + 1], dp + 1, x, y + 1);
         }
     } 
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。