# emu in blogjava

BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合 :: 管理 :: 171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks

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.

posted on 2005-12-13 12:00 emu 阅读(1551) 评论(19)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题 ### 评论

# emu的错误解法 2005-12-13 13:27 emu
public class WordPath
{
int resultCount;
public int countPaths(String[] grid, String find){
int rowCount = grid.length;
int cellCount=grid.length();
resultCount = 0;
char[][] charGrid = new char[rowCount][cellCount];
for(int y=0;y<rowCount;y++)
for(int x=0;x<cellCount;x++)
charGrid[y][x] = grid[y].charAt(x);
for(int y=0;y<rowCount;y++){
for(int x=0;x<cellCount;x++){
if(charGrid[y][x]==find.charAt(0)){
doCount(charGrid,find.substring(1),x,y);
}
if(resultCount<0) return -1;
}
}
return resultCount;
}
private void doCount(char[][] c,String find,int x,int y){
if(resultCount<0) return;
if(find.length()==0) {
resultCount++;
if(resultCount>10000000) resultCount=-1;
return;
}
if(y>0){
if(c[y-1][x]==find.charAt(0))
doCount(c,find.substring(1),x,y-1);
if(resultCount<0) return ;
if(x>0 && c[y-1][x-1]==find.charAt(0))
doCount(c,find.substring(1),x-1,y-1);
if(resultCount<0) return ;
if(x<c.length-1 && c[y-1][x+1]==find.charAt(0))
doCount(c,find.substring(1),x+1,y-1);
}
if(resultCount<0) return ;
if(y<(c.length-1)){
if(c[y+1][x]==find.charAt(0))
doCount(c,find.substring(1),x,y+1);
if(resultCount<0) return ;
if(x>0 && c[y+1][x-1]==find.charAt(0))
doCount(c,find.substring(1),x-1,y+1);
if(resultCount<0) return ;
if(x<c.length-1 && c[y+1][x+1]==find.charAt(0))
doCount(c,find.substring(1),x+1,y+1);
}
if(resultCount<0) return ;
if(x>0 && c[y][x-1]==find.charAt(0))
doCount(c,find.substring(1),x-1,y);
if(resultCount<0) return ;
if(x<c.length-1 && c[y][x+1]==find.charAt(0)){
doCount(c,find.substring(1),x+1,y);
}
return;
}

public static void main(String[] args){
WordPath w = new WordPath();
System.out.println(w.countPaths(new String[]{"ABC","FED","GHI"},"ABCDEFGHI"));
System.out.println(w.countPaths(new String[]{"ABC","FED","GAI"},"ABCDEA"));
System.out.println(w.countPaths(new String[]{"ABC","DEF","GHI"},"ABCD"));
System.out.println(w.countPaths(new String[]{"AA","AA"},"AAAA"));
System.out.println(w.countPaths(new String[]{"ABABA","BABAB","ABABA","BABAB","ABABA"},"ABABABBA"));
System.out.println(w.countPaths(new String[]{"AAAAA","AAAAA","AAAAA","AAAAA","AAAAA"},"AAAAAAAAAAA"));
System.out.println(w.countPaths(new String[]{"AB","CD"},"AA"));
}
}

回复  更多评论

# emu 更正的解法 2005-12-13 16:48 emu

public class WordPath {
public int countPaths(String[] grid, String find){
int rowCount = grid.length;
int cellCount=grid.length();
char[][] charGrid = new char[rowCount][cellCount];
int[][] m = new int[rowCount][cellCount],m1 = new int[rowCount][cellCount];
for(int y=0;y<rowCount;y++)
for(int x=0;x<cellCount;x++)
if (find.charAt(0)==(charGrid[y][x]=grid[y].charAt(x))) m[y][x]=1;
for(int i=1;i<find.length();i++){
char ch = find.charAt(i);
for(int y=0;y<rowCount;y++){
for(int x=0;x<cellCount;x++){
if(ch == charGrid[y][x]){
if(y>0){
if(x>0)m1[y][x]+=m[y-1][x-1];
m1[y][x]+=m[y-1][x];
if(x<cellCount-1) m1[y][x]+=m[y-1][x+1];
}
if(x>0)m1[y][x]+=m[y][x-1];
if(x<cellCount-1) m1[y][x]+=m[y][x+1];
if(y<rowCount-1){
if(x>0) m1[y][x]+=m[y+1][x-1];
m1[y][x]+=m[y+1][x];
if(x<cellCount-1) m1[y][x]+=m[y+1][x+1];
}
}
}
}
m=m1;m1= new int[rowCount][cellCount];
}
int result = 0;
for(int i=0;i<rowCount;i++)for(int j=0;j<cellCount;j++) if((result += m[i][j])>1000000000)return -1;
return result;
}

public static void main(String[] args){
WordPath w = new WordPath();
System.out.println(w.countPaths(new String[]{"ABC","FED","GHI"},"ABCDEFGHI"));
System.out.println(w.countPaths(new String[]{"ABC","FED","GAI"},"ABCDEA"));
System.out.println(w.countPaths(new String[]{"ABC","DEF","GHI"},"ABCD"));
System.out.println(w.countPaths(new String[]{"AA","AA"},"AAAA"));
System.out.println(w.countPaths(new String[]{"ABABA","BABAB","ABABA","BABAB","ABABA"},"ABABABBA"));
System.out.println(w.countPaths(new String[]{"AAAAA","AAAAA","AAAAA","AAAAA","AAAAA"},"AAAAAAAAAAA"));
System.out.println(w.countPaths(new String[]{"AB","CD"},"AA"));
}
}
回复  更多评论

# 用动态规划，三重循环就能搞定 2005-12-13 17:42 zzs
11  回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-13 18:02 emu

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-14 10:19 zzs

回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-14 12:47 emu

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-14 18:12 灵犀

回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-14 21:55 emu

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-15 10:18 灵犀

回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-15 10:59 emu

回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-15 11:27 zming
emu,你的正确的代码自己运行需要多少秒时间？我只跑
System.out.println(w.countPaths(new String[]{"AAAAA","AAAAA","AAAAA","AAAAA","AAAAA"},"AAAAAAAAAAA"));

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-15 13:14 zming
emu,对不起,刚才测试的有问题,我运行了你的更正的解法的代码,速度的确很快!  回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-15 15:26 emu
:) 用动态规划，时间只是随参数大小线性增长的，再慢都很快  回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-15 15:52 emu

public class WordPath {
public long countPaths(String[] grid, String find){
int rowCount = grid.length;
int cellCount=grid.length();
char[][] charGrid = new char[rowCount][cellCount];
long[][] m = new long[rowCount][cellCount],m1 = new long[rowCount][cellCount];
for(int y=0;y<rowCount;y++)
for(int x=0;x<cellCount;x++)
if (find.charAt(0)==(charGrid[y][x]=grid[y].charAt(x))) m[y][x]=1;
for(int i=1;i<find.length();i++){
char ch = find.charAt(i);
for(int y=0;y<rowCount;y++){
for(int x=0;x<cellCount;x++){
if(ch == charGrid[y][x]){
if(y>0){
if(x>0)m1[y][x]+=m[y-1][x-1];
m1[y][x]+=m[y-1][x];
if(x<cellCount-1) m1[y][x]+=m[y-1][x+1];
}
if(x>0)m1[y][x]+=m[y][x-1];
if(x<cellCount-1) m1[y][x]+=m[y][x+1];
if(y<rowCount-1){
if(x>0) m1[y][x]+=m[y+1][x-1];
m1[y][x]+=m[y+1][x];
if(x<cellCount-1) m1[y][x]+=m[y+1][x+1];
}
}
}
}
m=m1;m1= new long[rowCount][cellCount];
}
long result = 0;
for(int i=0;i<rowCount;i++)for(int j=0;j<cellCount;j++) if(m[i][j]<0||(result += m[i][j])<0)return -1;
return result;
}

public static void main(String[] args){
WordPath w = new WordPath();
System.out.println(w.countPaths(new String[]{"ABC","FED","GHI"},"ABCDEFGHI"));
System.out.println(w.countPaths(new String[]{"ABC","FED","GAI"},"ABCDEA"));
System.out.println(w.countPaths(new String[]{"ABC","DEF","GHI"},"ABCD"));
System.out.println(w.countPaths(new String[]{"AA","AA"},"AAAA"));
System.out.println(w.countPaths(new String[]{"ABABA","BABAB","ABABA","BABAB","ABABA"},"ABABABBA"));
System.out.println(w.countPaths(new String[]{"AAAAA","AAAAA","AAAAA","AAAAA","AAAAA"},"AAAAAAAAAAA"));
System.out.println(w.countPaths(new String[]{"AB","CD"},"AA"));
System.out.println(w.countPaths(new String[]{"AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA"},"AAAAAAAAAAAAAAAAAAAA"));
System.out.println(w.countPaths(new String[]{"AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA","AAAAAAAA"},"AAAAAAAAAAAAAAAAAAAAA"));
}
}

回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-15 17:08

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-15 18:00 灵犀

回复  更多评论

回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-17 01:12 emu

# re: google中国编程挑战赛资格赛真题 -- WordPath（750分） 2005-12-23 12:56 Tendy

http://blog.csdn.net/zmxj/archive/2005/12/13/551492.aspx

PS:

回复  更多评论

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: