POJ 3050 -- Hopscotch

http://poj.org/problem?id=3050
The cows play the child's game of hopscotch in a non-traditional way. Instead of a linear set of numbered boxes into which to hop, the cows create a 5x5 rectilinear grid of digits parallel to the x and y axes.

They then adroitly hop onto any digit in the grid and hop forward, backward, right, or left (never diagonally) to another digit in the grid. They hop again (same rules) to a digit (potentially a digit already visited).

With a total of five intra-grid hops, their hops create a six-digit integer (which might have leading zeroes like 000201).

Determine the count of the number of distinct integers that can be created in this manner.

http://www.cnblogs.com/7hat/p/3603697.html

题意：给定一个5*5的地图，每个格子上有一个数字。从一个格子出发（上下左右4个方向），走5步将数字连起来可以构造出一个6位数。问该地图可以构造出多少个不同的6位数。

分析：可以对每个格子做深度优先遍历，构造出所有数字，但要注意不要重复计数。在这里，我使用了set来保存已构造出的数字，结果就是set中的元素个数。

int a[5][5];
10 set<int> st;                //保存已构造的数字
12 const int dx[4] = {-1, 1, 0, 0};
13 const int dy[4] = {0, 0, -1, 1};
15 //深度优先遍历所有可能的构造
16 void dfs(int x, int y, int k, int num){
17     if(k == 6){
18         st.insert(num);
19         return;
20     }
21     for(int i = 0; i < 4; i ++){
22         int nx = x + dx[i], ny = y + dy[i];
23         if(0 <= nx && nx < 5 && 0 <= ny && ny < 5){ 
24             k ++;
25             dfs(nx, ny, k, num * 10 + a[nx][ny]);
26             k --;
27         }
28     }
29 }
30 
31 void solve(){
32     //对每个点作为起点，做深度优先遍历构造序列
33     for(int i = 0; i < 5; i ++){
34         for(int j = 0; j < 5; j ++){
35             dfs(i, j, 1, a[i][j]);
36         }
37     }
38     printf("%d\n", st.size());
39 }
40 
41 int main(int argc, char const *argv[]){
42 
43     for(int i = 0; i < 5; i ++){
44         for(int j = 0; j < 5; j ++)
45             scanf("%d", &a[i][j]);
46     }
47     solve();
48 
49     return 0;
50 }

Read full article from 3050 -- Hopscotch