- 论坛徽章:
- 0
|
WordPaths
Problem Statement
????
You are given a String[] grid representing a rectangular grid of letters. You are also given a String find, a word you are to find within the grid. The starting point may be anywhere in the grid. The path may move up, down, left, right, or diagonally from one letter to the next, and may use letters in the grid more than once, but you may not stay on the same cell twice in a row (see example 6 for clarification).
You are to return an int indicating the number of ways find can be found within the grid. If the result is more than 1,000,000,000, return -1.
Definition
????
Class:
WordPath
Method:
countPaths
Parameters:
String[], String
Returns:
int
Method signature:
int countPaths(String[] grid, String find)
(be sure your method is public)
????
Constraints
-
grid will contain between 1 and 50 elements, inclusive.
-
Each element of grid will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
-
Each element of grid will contain the same number of characters.
-
find will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
Examples
0)
????
{"ABC",
"FED",
"GHI"}
"ABCDEFGHI"
Returns: 1
There is only one way to trace this path. Each letter is used exactly once.
1)
????
{"ABC",
"FED",
"GAI"}
"ABCDEA"
Returns: 2
Once we get to the 'E', we can choose one of two directions for the final 'A'.
2)
????
{"ABC",
"DEF",
"GHI"}
"ABCD"
Returns: 0
We can trace a path for "ABC", but there's no way to complete a path to the letter 'D'.
3)
????
{"AA",
"AA"}
"AAAA"
Returns: 108
We can start from any of the four locations. From each location, we can then move in any of the three possible directions for our second letter, and again for the third and fourth letter. 4 * 3 * 3 * 3 = 108.
4)
????
{"ABABA",
"BABAB",
"ABABA",
"BABAB",
"ABABA"}
"ABABABBA"
Returns: 56448
There are a lot of ways to trace this path.
5)
????
{"AAAAA",
"AAAAA",
"AAAAA",
"AAAAA",
"AAAAA"}
"AAAAAAAAAAA"
Returns: -1
There are well over 1,000,000,000 paths that can be traced.
6)
????
{"AB",
"CD"}
"AA"
Returns: 0
Since we can't stay on the same cell, we can't trace the path at all.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
实现程序：
- public class WordPath {
-
- private char[][] charMatrix;
- private String key;
-
- private int x_min = 0;
- private int y_min = 0;
- private int x_max;
- private int y_max;
-
- private static final int MAX_NUMBER = 100000000;
- private static final int MAX_OPERATION = 8;
-
- public int countPaths(String[] grid, String find){
- this.key = find;
- this.buildMatrix(grid);
-
- int total = this.calculatePath(init());
-
- System.out.println("Total number of paths = " + total);
- return total <= MAX_NUMBER? total:-1;
- }
-
- private int[][] init(){
- char initKey = key.charAt(0);
- int[][] points = new int[x_max*y_max][2];
- int idx = -1;
- for(int i=x_min; i < x_max; i++){
- int jIdx = charMatrix[i].length;
- for(int j = 0;j<jIdx; j++){
- idx = addOperation(i, j, points, initKey, idx);
- }
- }
-
- int[][] res = idx == -1? null:trimIntArray(points, idx);
- return res;
- }
-
- private void buildMatrix(String[] elements){
- y_max = elements.length;
-
- for(int j = y_min; j<y_max; j++){
- char[] tmp = elements[j].toCharArray();
-
- //initialize stringMatrix
- if(charMatrix == null){
- x_max = tmp.length;
- charMatrix = new char[y_max][x_max];
- }
-
- System.arraycopy(tmp, 0, charMatrix[j], 0, x_max);
- }
-
- printArray(charMatrix);
- }
-
- /**
- * Return current char index of charMatrix
- * @param point
- * @param keyIdx
- * @return
- */
- private int calculatePath(int[][] point){
-
- if(point == null) return 0;
-
- int res = 0;
-
- for(int i=0; i < point.length; i++){
- int x = point[i][0];
- int y = point[i][1];
- System.out.println("\n#####################INITIAL SERACH at (" + x + ", " + y + ")####################");
- res += calculatePathFromPoint(x, y, 0);
- }
-
- return res;
- }
-
- private int calculatePathFromPoint(int x, int y, int currentIdx){
-
- if(currentIdx == key.length() -1){
- System.out.println("Searching complete!!! at point(" + x + ", " + y + ")");
- return 1;
- }else{
- currentIdx ++;
- System.out.println("Calculating from point (" + x + ", " + y + "), searching for " + key.charAt(currentIdx) + " with idx = " + currentIdx);
- int[][] nextPoints = getNextPoints(x, y, currentIdx);
-
- if(nextPoints == null) return 0;
-
- int count = nextPoints.length;
-
- int tmp = 0;
- for(int i=0;i<nextPoints.length;i++){
- int point_x = nextPoints[i][0];
- int point_y = nextPoints[i][1];
-
- tmp += calculatePathFromPoint(point_x, point_y, currentIdx);
- }
-
- return tmp;
-
- }
- }
-
- private int[][] getNextPoints(int point_x, int point_y, int keyIdx){
- //8 possible directions
- char keyChar = key.charAt(keyIdx);
-
- int[][] operation = new int[MAX_OPERATION][2];
-
- int idx = -1;
-
- idx = addOperation(point_x - 1, point_y,operation, keyChar, idx);
- idx = addOperation(point_x - 1, point_y - 1,operation, keyChar, idx);
- idx = addOperation(point_x - 1, point_y + 1,operation, keyChar, idx);
- idx = addOperation(point_x + 1, point_y, operation, keyChar, idx);
- idx = addOperation(point_x + 1, point_y - 1,operation, keyChar, idx);
- idx = addOperation(point_x + 1, point_y + 1,operation, keyChar, idx);
- idx = addOperation(point_x, point_y + 1,operation, keyChar, idx);
- idx = addOperation(point_x, point_y - 1,operation, keyChar, idx);
-
-
- return idx == -1? null:trimIntArray(operation, idx);
- }
-
-
- private int addOperation(int x, int y, int[][] operation, final char keyChar, int idx){
- if(!isOutOfRange(x, y)){
- if(keyChar == charMatrix[x][y]){
- idx ++;
- operation[idx][0] = x;
- operation[idx][1] = y;
- }
- }
- return idx;
- }
-
- private boolean isOutOfRange(int x, int y){
-
- return (x > x_max-1 || x < x_min || y > y_max-1 || y< y_min);
- }
-
-
- private static int[][] trimIntArray(int[][] arr, int lastIdx){
- int column = arr[0].length;
- int[][] res = new int[lastIdx + 1][column];
-
- for(int i =0; i<lastIdx +1; i++){
- for(int j = 0; j < column; j ++)
- res[i][j] = arr[i][j];
- }
- //printArray(res);
- return res;
- }
-
-
- private static void printArray(char[][] args){
- System.out.println("===============================================");
- for(int i=0;i<args.length;i++){
- System.out.print("{");
- for(int j=0;j< args[i].length;j++){
- System.out.print(args[i][j] + ((j == args[i].length - 1)? "":","));
- }
- System.out.print("}");
- System.out.println();
- }
- System.out.println("===============================================");
- }
-
- private static void printArray(int[][] args){
- System.out.println("===============================================");
- for(int i=0;i<args.length;i++){
- System.out.print("{");
- for(int j=0;j< args[i].length;j++){
- System.out.print(args[i][j] + ((j == args[i].length - 1)? "":","));
- }
- System.out.print("}");
- System.out.println();
- }
- System.out.println("===============================================");
- }
-
-
- public static void main(String[] arg){
- String find = "ABABABBA";
- String[] val = {"ABABA", "BABAB", "ABABA", "BABAB", "ABABA"};
-
- System.out.println("Keys to be Found");
- System.out.println(find);
- new WordPath().countPaths(val, find);
- }
-
- public static void usage(){
- System.out.println("java WordPath strRow1, strRow2, .... strRowN, stringToBeFound");
- }
-
- public static void validateArguments(String[] args){
- if(args == null || args.length <= 1){
- usage();
- System.exit(0);
- }
-
- try{
- Integer.parseInt(args[args.length-1]);
- }catch(Exception e){
- usage();
- System.exit(0);
- }
-
- int len = args[0].length();
- for(int i=1; i<args.length -1; i ++){
- if(len != args[i].length()){
- System.out.println("Not all city map row are equal in length");
- System.exit(0);
- }
- }
- }
- }
|
|
免费注册
发表于 2005-12-20 11:43
，但还称之为俺的题解吧，但其实俺仅是把程序读懂了而已，还没理解……
