Google™ Code Jam 中国编程挑战赛资格赛2005年12月12日中午12时-13日中午12时在线举行，参赛者会抽到5组题中的1组，每组题有2道难度不同的题目，分数各为250和750，难度高的题目分数较高。参赛者有60分钟可以完成全部的2题或其中1题。我抽到的是第3组题，以237.97分的成绩晋级下一轮比赛，在入围的500名参赛者中排名第189位。

Qualification Groups 3/7/15/17/23 Problem 250 Statement

You have several identical balls that you wish to place 

 1 public class FillBaskets
 2 {
 3   public int countWays(int baskets, int capacity, int balls)
 4   {
 5     if (baskets * capacity < balls) return 0;
 6     if (baskets == 1) return 1;
 7     int n = 0;
 8     int b = (balls < capacity ? balls : capacity);
 9     for (int i = 0; i <= b; i++)
10     {
11       n += countWays(baskets - 1, capacity, balls - i);
12     }
13     return n;
14   }
15 }

 250分的题比较简单，使用递归可以了。

Qualification Groups 3/7/15/17/23 Problem 750 Statement

You are given a 

 1 public class WordPath
 2 {
 3   const int MAX = 1000000000;
 4   int[,] g;
 5   int[]  f;
 6   int    flen;
 7   
 8   int paths(int i0, int j0, int k)
 9   {
10     if (k == flen) return 1;
11     int n = 0;
12     for (int i = i0 - 1; i <= i0 + 1; i++)
13     {
14       for (int j = j0 - 1; j <= j0 + 1; j++)
15       {
16         if (i == i0 && j == j0) continue;
17         if (f[k] == g[i, j])
18         {
19           n += paths(i, j, k+1);
20           if (n > MAX) return MAX + 1;
21         }
22       }
23     }
24     return n;
25   }
26   
27   public int countPaths(string[] grid, string find)
28   {
29     flen = find.Length;
30     f    = new int[flen];
31     for (int i = 0; i < flen; i++)
32     {
33       f[i] = find[i];
34     }
35     int rows = grid.Length;
36     int cols = grid[0].Length;
37     g = new int[rows+2, cols+2];
38     for (int i = 0; i < rows; i++)
39     {
40       for (int j = 0; j < cols; j++)
41       {
42         g[i+1, j+1] = grid[i][j];
43       }
44     }
45     int n = 0;
46     for (int i = 1; i <= rows; i++)
47     {
48       for (int j = 1; j <= cols; j++)
49       {
50         if (f[0] == g[i, j])
51         {
52           n += paths(i, j, 1);
53           if (n > MAX) return -1;
54         }
55       }
56     }
57     return n;
58   }
59 }

750分的题我也使用了递归，结果对 Example 5 的输入计算时间超过2秒而在系统测试阶段被判为0分。资格赛结束后看了 happyyellow 的解答：

 1 using System.Drawing;
 2 using System.Collections;
 3 
 4 public class WordPath
 5 {
 6   public int countPaths(string[] grid, string find)
 7   {
 8     ArrayList[] lists = new ArrayList[26];
 9     for (int i = 0; i < lists.Length; i++)
10     {
11       lists[i] = new ArrayList();
12     }
13     
14     int il = grid.Length;
15     int jl = grid[0].Length;
16     for (int i = 0; i < il; i++)
17     {
18       for (int j = 0; j < jl; j++)
19       {
20         lists[grid[i][j] - 'A'].Add(new Point(i+1, j+1));
21       }
22     }
23     
24     long[,] m = new long[il+2, jl+2];
25     foreach (Point p in lists[find[0] - 'A'])
26     {
27       m[p.X, p.Y] = 1;
28     }
29     for (int d = 1; d < find.Length; d++)
30     {
31       long[,] mm = new long[il+2, jl+2];
32       foreach (Point p in lists[find[d] - 'A'])
33       {
34         mm[p.X, p.Y] =
35           m[p.X-1, p.Y+1] + m[p.X, p.Y+1] + m[p.X+1, p.Y+1] +
36           m[p.X-1, p.Y  ] +                 m[p.X+1, p.Y  ] +
37           m[p.X-1, p.Y-1] + m[p.X, p.Y-1] + m[p.X+1, p.Y-1];
38       }
39       m = mm;
40     }
41     long n = 0;
42     for (int i = 1; i <= il; i++)
43     {
44       for (int j = 1; j <= jl; j++)
45       {
46         n += m[i, j];
47       }
48     }
49     if (n > 1000000000) return -1;
50     return (int)n;
51   }
52 }