1.原题:http://poj.org/problem?id=3009。题意是冰壶游戏,给定若干组的地图,W表示宽度(列数)H表示高度(行数)。然后接下来的H行W列就是地图数据。0表示没有障碍 1表示障碍 2表示起点 3表示终点。程序的目的是给定一个起点和一个终点,求出满足下列规则的最小的移动数目。
规则:
A.每次冰壶碰到障碍,可以用捆棍子向上下左右移动,并且冰壶的轨迹沿推出的方向。
B.如果冰壶出界、没有路可走或者是10次移动操作内不能到达终点,那么游戏失败输出-1。否则需要求出最小的移动操作
C.冰壶碰到障碍的话,障碍会消失。
2.思路:可以用DFS相四个方向探测,然后临时标记一下起始点,注意我们要沿着方向走,所以需要一个循环一直探测到没有障碍的位置(如果是之前访问的位置没关系,那肯定会失败。)。如果探测打那个点是障碍,那么临时移除他,然后dfs,深度+1;如果是终点,比较最小值;如果是普通的点,就直接dfs,深度+1。递归的基线条件就是depth(深度)>10(从1开始的)
3.代码:
#include <cstdio> #include <vector> #include <algorithm> enum Node { NO = 0, BLOCK, START, GOAL }; const int MAX_W = 20; const int MAX_H = 20; int map[MAX_W][MAX_H]; //int flag[MAX_W][MAX_H]; int res[100] = { 0 }; int w, h; const int limit = 10; int minopt = limit + 1; int dir[4][2] = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } };//四个方向 bool dfs(int depth, int x, int y) { if (depth >limit) { //fail the game return false; } int dx, dy; for (int i = 0; i<4; ++i) { dx = x + dir[i][0]; dy = y + dir[i][1]; if (dx >= 0 && dx <h && dy >= 0 && dy <w && map[dx][dy] !=BLOCK) { //合法的点 那么需要项这个方向递增移动到下一个组块之前 然后进行dfs int nx = dx, ny = dy; for (; nx >= 0 && nx <h && ny >= 0 && ny <w && (map[nx][ny] == NO || map[nx][ny]==START); nx = nx + dir[i][0], ny = ny + dir[i][1]) ; if (nx <0 || nx >= h || ny <0 || ny >= w) continue; //if (flag[nx][ny] == 1)//这个根本没什么用 因为冰壶会把之前的进过的位置全部撞开 所以我只需要讨论下一步是否出界或者是撞到块的情况 //continue; if (map[nx][ny] == GOAL) { minopt = std::min(minopt, depth); continue; } if (map[nx][ny] == BLOCK) { //HIT IT REMOVE; map[nx][ny] = NO; //flag[x][y] = 1; dfs(depth + 1, nx - dir[i][0], ny - dir[i][1]); //flag[x][y] = 0; map[nx][ny] = BLOCK; } else { //flag[x][y] = 1; dfs(depth + 1, nx - dir[i][0], ny - dir[i][1]); //flag[x][y] = 0; } } } } int main() { int r = 0; while (~scanf("%d %d", &w, &h) && w != 0 && h != 0) { int bx, by; for (int i = 0; i<h; ++i) { for (int j = 0; j<w; ++j) { scanf("%d", &map[i][j]); if (map[i][j] == START) bx = i, by = j; } } //地图准备完毕了 dfs(1, bx, by); if (minopt == limit + 1) { res[r++] = -1; } else { res[r++] = minopt; } minopt = limit + 1; } for (int i = 0; i<r; ++i) { if (res[i] != 0) printf("%d\n", res[i]); } return 0; }