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.
Java的解答
public class WordPath
{
public int countPaths(String[] grid, String find)
{
mx = grid.length;
my = grid[0].length();
charRect = new char[grid.length][];
for(int i=0;i<charRect.length;i++)
charRect[i] = grid[i].toCharArray();
finds = find.toCharArray();
int count = 0;
char first = finds[0];
for(int x=0;x<charRect.length;x++)
for(int y=0;y<charRect[x].length;y++)
if (charRect[x][y] == first)
count += countPaths(0,x,y);
if (count > 1000000000)
return -1;
return count;
}
char[][] charRect = null;
char[] finds = null;
int mx = 0;
int my = 0;
private int countPaths(int ind,int cx,int cy)
{
if (ind == finds.length - 1)
return 1;
int count = 0;
char nextChar = finds[ind+1];
for(int dx=-1;dx<=1;dx++)
{
for(int dy=-1;dy<=1;dy++)
{
if (dx==0 && dy == 0)
continue;
int x = cx + dx;
int y = cy + dy;
if (x >=0 && x< mx && y >= 0 && y < my)
{
if (charRect[x][y] == nextChar)
count += countPaths(ind+1,x,y);
}
}
}
return count;
}
分享到:
相关推荐
少儿编程-少儿编程系统-少儿编程系统源码-少儿编程管理系统-少儿编程管理系统java代码-少儿编程系统设计与实现-基于ssm的少儿编程系统-基于Web的少儿编程系统设计与实现-少儿编程网站-少儿编程网站代码-少儿编程平台...
编程训练-编程训练系统-编程训练系统源码-编程训练管理系统-编程训练管理系统java代码-编程训练系统设计与实现-基于springboot的编程训练系统-基于Web的编程训练系统设计与实现-编程训练网站-编程训练网站代码-编程...
少儿编程-少儿编程系统-少儿编程系统源码-少儿编程管理系统-少儿编程管理系统java代码-少儿编程系统设计与实现-基于ssm的少儿编程系统-基于Web的少儿编程系统设计与实现-少儿编程网站-少儿编程网站代码-少儿编程平台...
编程训练-编程训练系统-编程训练系统源码-编程训练管理系统-编程训练管理系统java代码-编程训练系统设计与实现-基于springboot的编程训练系统-基于Web的编程训练系统设计与实现-编程训练网站-编程训练网站代码-编程...
Google编程大赛题目Google编程大赛题目Google编程大赛题目
Google C++编程风格指南-中文版,Google 发布自己的编程风格
Google中国编程大赛入围赛真题
商业编程-源码-Google搜索客户端API示例代码.zip
商业编程-源码-Google地图 for Gnuboard v4.32.13.zip
工作需要,将这个 Mellanox 的编程用户手册(RDMA_Aware_Programming_user_manual.pdf)翻译成了中文,便于大家 学习参考。其中第一章和第二章参考了网络上的一些已有翻译,并做了部分纠 错。其他借助了 google 翻译。...
谷歌浏览器rpm安装包 版本google-chrome-stable-118.0.5993.88-1.x86_64
2017年第四届APP INVENTOR应用开发全国中学生挑战赛特等奖、一等奖、二等奖(高中组)适合小朋友自学, Scratch是MIT开发的完全免费的针对儿童学习编程而设计的开源软件。 这个软件的特点是: 使用者可以不认识英文...
商业编程-源码-无刷新仿google波形扭曲彩色Asp.net验证码.zip
Google_C++编程风格指南-加强整理中文版 祝大家学习进步!