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[0].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[0].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[0].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[0].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"));
}
}

时间复杂度太高。当时没有好好想想。和alphabet同出一辙啊!该死!
  回复  更多评论
  

# emu 更正的解法 2005-12-13 16:48 emu
看看,和alphabet是不是一样:

public class WordPath {
    public int countPaths(String[] grid, String find){
        int rowCount = grid.length;
        int cellCount=grid[0].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
你用的java我没看:)。对JAVA不是很懂。
不过貌似状态是三维的吧。
递推状态矩阵State[k][i][j]表示第k步时第[i,j]点的累计方法数。
差不多这样子。



  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- WordPath(750分) 2005-12-14 12:47 emu
上回贴的时候没有做好符号替换,贴出来的代码很多都显示不出来,刚刚才发现。难怪你看了觉得不象动态规划。
递推的过程只需要保留上一步骤的结果和当前计算中的步骤的中间结果就可以了,没有必要用三维数组保存全部推导状态。  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- WordPath(750分) 2005-12-14 18:12 灵犀
初赛比的是速度,怎么简单怎么写。
google在出题上并没有在时间和空间上给予难度。
数据都相当小= =
居然只有50。。。。
  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- WordPath(750分) 2005-12-14 21:55 emu
>>google在出题上并没有在时间和空间上给予难度。
其实还是会有的。上次东亚我记得是8秒,这次有人说限定是2秒。这个要求对于正确的算法是非常宽松的,但是对于错误的算法就是一个过不去的坎了。象这道题,我第一次的解法就是在时间复杂度上有问题。  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- WordPath(750分) 2005-12-15 10:18 灵犀
恩~你说的没错,时限是两秒。
以前的比赛你参加了?
那是什么比赛呢?
  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- WordPath(750分) 2005-12-15 10:59 emu
就是今年的东亚code jam大赛啊。不过在资格赛就刷下来了,我觉得有点冤的,入围的不见得都是什么高手。模拟题和资格赛题收集在http://www.blogjava.net/emu/category/2769.html
  回复  更多评论
  

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

# 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[0].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
这里能贴 c# 么? 怯怯的问。。。
我也写了一个解法  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- WordPath(750分) 2005-12-15 18:00 灵犀
我这是第一次参加CodeJam的比赛。
呵呵~算是菜鸟拉。
我的测了最大的数据(50*50个"A"),然后给出一个长度为50的全"A"串,
用它的系统测大概是0.01s
  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- WordPath(750分) 2005-12-16 16:56 RoadNorth
我也做了一个解法,用C++

http://blog.csdn.net/RoadNorth/archive/2005/12/16/554027.aspx


欢迎大家指正。

  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- WordPath(750分) 2005-12-17 01:12 emu
你的解法倒是很别出心裁,有必要一定要倒过来查吗,正着查不是一样?
不过看看代码量,估计是超过1个小时的。  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- WordPath(750分) 2005-12-23 12:56 Tendy
我做了一个,回复在
http://blog.csdn.net/zmxj/archive/2005/12/13/551492.aspx
运行第五个例子大概花了 2 分钟(CPU PIII 866MHZ,内存512M)
PS:
我的代码如果要连续运行所有example,
要在函数 int countPaths(String[] grid, String find)
里面加一句 total = 0;
  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: