一场冰面角逐在一个矩形区域进行，区域上设置有障碍(1暗示)，空白区域(0暗示)，起点(2暗示)，终点(3暗示)。起始在起点有一个石头，每次将它向上左下右四个标的目的之一抛出(当某一标的目的上临近有障碍时不能向这一标的目的抛出)，石块将沿这一标的目的运动，直到：

石头撞到了障碍：石头停在靠近障碍的阿谁空格上，障碍消掉

石头超过了矩形区域的范畴，此次抛出无效

达到终点

一局游戏一共可以抛掷石头10次，，如果10次后石头还没有达到终点，那么游戏掉败。需要达到终点的最少抛掷次数。

样例输入：

2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3
0 0

样例输出：

1
4
-1
4
10
-1

思路：

_throw()函数模拟每次石头向某一标的目的运动，返回三种功效：出界、达到终点、遇到障碍。

按照抛出的三种功效，出界则转向下一标的目的测验考试，达到终点则更新最终步数，遇到障碍则继续递归到新一状态，从这一状态开始从头将石头向四个标的目的扔出。注意保存现场。

代码：

#include <iostream> #include <utility> using namespace std; typedef pair<int, int> PII; const int N = 22; const int dr[] = {0, 1, -1, 0}; const int dc[] = {1, 0, 0, -1}; int m, n; int end_r, end_c; //终点的坐标 int g[N][N]; int cnt, steps; int _throw(int start_r, int start_c, int dir, PII &end_point){ int raw = start_r, col = start_c; while(1){ raw += dr[dir]; col += dc[dir]; // printf("cur_r: %d cur_c: %d\n", raw, col); if(raw < 0 || raw >= m || col < 0 || col >= n){ // outside end_point.first = start_r; end_point.second = start_c; return 0; } if(raw == end_r && col == end_c){ //arrive the end point return 1; } if(g[raw][col] == 1){ //arrive a block end_point.first = raw - dr[dir]; end_point.second = col - dc[dir]; return 2; } } } void dfs(int start_x, int start_y){ if(cnt > 10) return; int condition; for(int dir = 0; dir < 4; ++dir){ PII end_point; end_point.first = start_x; end_point.second = start_y; int tmpr = start_x + dr[dir]; int tmpc = start_y + dc[dir]; //用于判断“起点”四周是否有障碍否决抛出 if(tmpr>=0 && tmpr<m && tmpc>=0 && tmpc < n && g[tmpr][tmpc] != 1){ //当四周没有blocks时可以throw condition = _throw(start_x, start_y, dir, end_point); if(condition == 0) continue; if(condition == 1){ //达到终点 if(cnt+1 < steps) {steps = cnt+1;} //更新最少达到的功效到steps中 continue; } if(condition == 2) { int old_cnt = cnt; //保存当前状态的步数 cnt++; g[end_point.first+dr[dir]][end_point.second+dc[dir]] = 0; //断根障碍 dfs(end_point.first, end_point.second); //进入下一状态 g[end_point.first+dr[dir]][end_point.second+dc[dir]] = 1; //恢复现场 cnt = old_cnt; } } } } int main(){ //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int start_r, start_c; while(scanf("%d%d", &n, &m) && m != 0){ for(int i = 0; i < m; ++i){ for(int j = 0; j < n; ++j){ scanf("%d", &g[i][j]); if(g[i][j] == 2){ start_r = i; start_c = j;} if(g[i][j] == 3) { end_r = i; end_c = j;} } } cnt = 0, steps = 100000; dfs(start_r, start_c); if(steps>10) printf("-1\n"); else printf("%d\n", steps); } }

poj3009 Curling 2.0