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

### 1.问题描述

```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)一定要 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.```

### 2.代码示例

```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");
}
}```

0 条评论

• ### 前端基础-JavaScript流程控制

执行顺序：1243 ---- 243 -----243(直到循环条件变成false)

• ### 自己写个类加载器

获取指定包下所有的类，需要将包名转换为文件路径，读class文件或者jar包，再去进行类加载：

• ### leetcode-125-Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric c...

• ### 1028 人口普查 (20 分)测试点3格式错误

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### 全球34家金融科技独角兽：中国企业包揽前三甲，美国有18家入围！

过去几年金融科技非常热门，天使投资者和风险投机构投入了数亿美元，甚至数十亿美元的资金。仅仅在2017年，根据毕马威的数据，金融科技企业就获得了惊人的310亿美元...

• ### 使用Artik创建物联网项目

Artik IoT平台是一个端到端的物联网平台，可协助我们构建出物联网项目。它是一个开放的平台，对多种不同设备提供云支持。通过Artik IoT，成功连接的设备...

• ### C#网络编程(异步传输字符串) - Part.3

这篇文章我们将前进一大步，使用异步的方式来对服务端编程，以使它成为一个真正意义上的服务器：可以为多个客户端的多次请求服务。但是开始之前，我们需要解决上一节中遗留...