经典算法题-矩阵中查找单词路径数

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).
你会得到一个字符串的数组，表示一个字符的矩阵，你还会得到一个字符串查找，需要在矩阵中查找这个单词，单词的开始点可能在矩阵的任意位置，方向可以是上，下，左，右，或者对角，也可能多次使用矩阵中的字符，但是你不可以在同一行的相同单元中两次。见例6

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.
你需要返回一个整数，表示在矩阵中发现的路径个数，如果返回的路径超过 1,000,000,000，就返回 -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)一定要 public 


Constraints
约束条件
-
grid will contain between 1 and 50 elements, inclusive.
矩阵包含 1-50 个元素
-
Each element of grid will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
每一个元素包含 1-50 个大写字母 'A'-'Z'
-
Each element of grid will contain the same number of characters.
每一个元素包含相同数目的字符
-
find will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
查找的单词包含 1-50 个字符

Examples
举例
0)

{"ABC",
 "FED",
 "GHI"}
"ABCDEFGHI"
Returns: 1
返回 1
There is only one way to trace this path. Each letter is used exactly once.
只有一个路径可以查到

1)


{"ABC",
 "FED",
 "GAI"}
"ABCDEA"
Returns: 2
返回 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
返回 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
返回 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
返回 56448
There are a lot of ways to trace this path.
5)


{"AAAAA",
 "AAAAA",
 "AAAAA",
 "AAAAA",
 "AAAAA"}
"AAAAAAAAAAA"
Returns: -1
返回 -1

There are well over 1,000,000,000 paths that can be traced.
这个将超过 1,000,000,000 种路径，返回 -1
6)

????
{"AB",
 "CD"}
"AA"
Returns: 0
返回 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 {
	int m,n,count=0;
	char[] word;
	char[][] matrix;
	public int countPaths(String[] grid, String find) {
		m=grid.length;
		n=grid[0].length();
		matrix=new char[m][n];
		word=find.toCharArray();
		int i,j;
		for (i=0;i<m;i++) {
			for (j=0;j<n;j++) {
				matrix[i][j]=grid[i].charAt(j);
			}
		}
		for (i=0;i<m;i++) {
			for (j=0;j<n;j++) {
				if (matrix[i][j]==word[0]) {
					findNextChar(i,j,1);
				}
			}
		}
		if (count>1000000000)
			count=-1;
		return count;
	}
	boolean findNextChar(int x,int y,int c) {
		boolean found=false,findnext=false;
		if (x-1>=0&&x-1<m&&y-1>=0&&y-1<n) {
			if (matrix[x-1][y-1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x-1,y-1,c+1))
						findnext=true;
				}
			}
		}
		if (x-1>=0&&x-1<m&&y>=0&&y<n) {
			if (matrix[x-1][y]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x-1,y,c+1))
						findnext=true;
				}
			}
		}
		if (x-1>=0&&x-1<m&&y+1>=0&&y+1<n) {
			if (matrix[x-1][y+1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x-1,y+1,c+1))
						findnext=true;
				}
			}
		}
		if (x>=0&&x<m&&y-1>=0&&y-1<n) {
			if (matrix[x][y-1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x,y-1,c+1))
						findnext=true;
				}
			}
		}
		if (x>=0&&x<m&&y+1>=0&&y+1<n) {
			if (matrix[x][y+1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x,y+1,c+1))
						findnext=true;
				}
			}
		}
		if (x+1>=0&&x+1<m&&y-1>=0&&y-1<n) {
			if (matrix[x+1][y-1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x+1,y-1,c+1))
						findnext=true;
				}
			}	
		}
		if (x+1>=0&&x+1<m&&y>=0&&y<n) {
			if (matrix[x+1][y]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x+1,y,c+1))
						findnext=true;
				}
			}
		}
		if (x+1>=0&&x+1<m&&y+1>=0&&y+1<n) {
			if (matrix[x+1][y+1]==word[c]) {
				found=true;
				if (count>1000000000) {
					return false;
				}
				if (c==word.length-1) {
					count++;
					findnext=true;
				}
				else {
					if (findNextChar(x+1,y+1,c+1))
						findnext=true;
				}
			}
		}
		if (found&&findnext)
			return true;
		else return false;
	}
}

public class WordTest {
	public static boolean Test1() {
		WordPath wp=new WordPath();
		String[] grid={"ABC",
					   "FED",
					   "GHI"};
		String find="ABCDEFGHI";
		int key=1;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test2() {
		WordPath wp=new WordPath();
		String[] grid={"ABC",
					   "FED",
					   "GAI"};
		String find="ABCDEA";
		int key=2;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test3() {
		WordPath wp=new WordPath();
		String[] grid={"ABC",
					   "DEF",
					   "GHI"};
		String find="ABCD";
		int key=0;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test4() {
		WordPath wp=new WordPath();
		String[] grid={"AA",
                       "AA"};
		String find="AAAA";
		int key=108;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test5() {
		WordPath wp=new WordPath();
		String[] grid={"ABABA",
					   "BABAB",
					   "ABABA",
					   "BABAB",
					   "ABABA"};
		String find="ABABABBA";
		int key=56448;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test6() {
		WordPath wp=new WordPath();
		String[] grid={"AAAAA",
					   "AAAAA",
					   "AAAAA",
					   "AAAAA",
					   "AAAAA"};
		String find="AAAAAAAAAAA";
		int key=-1;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static boolean Test7() {
		WordPath wp=new WordPath();
		String[] grid={"AB",
                       "CD"};
		String find="AA";
		int key=0;
		int result=wp.countPaths(grid,find);
		System.out.println (result);
		return result==key;
	}
	public static void main(String[] args) {
		if (Test1())
			System.out.println ("Test1 OK");
		if (Test2())
			System.out.println ("Test2 OK");
		if (Test3())
			System.out.println ("Test3 OK");
		if (Test4())
			System.out.println ("Test4 OK");
		if (Test5())
			System.out.println ("Test5 OK");
		if (Test6())
			System.out.println ("Test6 OK");
		if (Test7())
			System.out.println ("Test7 OK");
	}
}