首页 > 专题系列 > Java解POJ > POJ 1154 LETTERS [解题报告] Java
2013
11-09

POJ 1154 LETTERS [解题报告] Java

LETTERS

问题描述 :

A single-player game is played on a rectangular board divided in R rows and C columns. There is a single uppercase letter (A-Z) written in every position in the board.

Before the begging of the game there is a figure in the upper-left corner of the board (first row, first column). In every move, a player can move the figure to the one of the adjacent positions (up, down,left or right). Only constraint is that a figure cannot visit a position marked with the same letter twice.

The goal of the game is to play as many moves as possible.

Write a program that will calculate the maximal number of positions in the board the figure can visit in a single game.

输入:

The first line of the input contains two integers R and C, separated by a single blank character, 1 <= R, S <= 20.

The following R lines contain S characters each. Each line represents one row in the board.

输出:

The first and only line of the output should contain the maximal number of position in the board the figure can visit.

样例输入:

3 6
HFDFFB
AJHGDH
DGAGEH

样例输出:

6

解题代码:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

    private static String[] a = null;
    private static int max = -1;
    private static int n = 0;
    private static int m = 0;

    private static void dfs(int x, int y, char[] c, int current) {
        boolean find = false;
        for (int i = 0; i < current; i++) {
            if (c[i] == a[x].charAt(y)) {
                find = true;
                break;
            }
        }

        if (find) {
            max = Math.max(max, current);
            return;
        }

        c[current] = a[x].charAt(y);

        if (x - 1 >= 0) {
            dfs(x - 1, y, c, current + 1);
        }

        if (x + 1 < n) {
            dfs(x + 1, y, c, current + 1);
        }

        if (y - 1 >= 0) {
            dfs(x, y - 1, c, current + 1);
        }

        if (y + 1 < m) {
            dfs(x, y + 1, c, current + 1);
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        String line = stdin.readLine();
        String[] temp = line.split("[ ]+");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        a = new String[n + 1];
        for (int i = 0; i < n; i++) {
            a[i] = stdin.readLine();
        }

        char[] c = new char[30];
        dfs(0, 0, c, 0);
        System.out.println(max);
    }

}

  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)