# POJ 3050 Hopscotch

Contents

There is a 5 * 5 array filled with integers. You can only go up, down, left and right. You can start on any point in the array and can only move 5 times. Therefore, you will get 6 integers.

Find the number of distinct integers you can constructed.

### Solution

I use a set to avoid same sequences. Since there are only 6 steps and the array is only 5*5, dfs each point, add into the set.

I used to_string() at first but got compile error on POJ, then I use stringstream but got TLE. DO NOT USE sstream, it’s just too slow! Slower than molasses!

Finally, I got AC.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45  #include #include #include using namespace std; set ans; int m[5][5]; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }; string s; void dfs(int x, int y, int n) { if (n == 0) { ans.insert(s); return; } for (int i = 0; i < 4; i++) { int tx = x+dx[i]; int ty = y+dy[i]; if (tx >= 0 && tx < 5 && ty >= 0 && ty < 5) { string str = s; s += m[tx][ty]; dfs(tx, ty, n-1); s = str; } } return ; } int main(void) { for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) cin >> m[i][j]; } for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { s = ""; dfs(i, j, 6); } } cout << ans.size() << endl; return 0; }