本文主要是介绍POJ 3009 *** Curling 2.0，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意:有一个h*w的棋盘，某些棋盘上的位置有冰块。打冰球的游戏，对于冰球而言只能向上下左右运动，且会一直运动直到遇到有冰块的位置，或者出界。如果遇到有冰块的位置，则将冰块打碎，冰球停留在往冰块方向上的前一个位置上。如果出界则出局。问最短到达目标需要多少步。（最多只能打10次）
想法:dfs+回溯。
代码如下：
#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<cstring>
#include<sstream>
#include<set>
#include<string>
#include<iterator>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
struct Position {int x, y;
};//当前位置
int w, h, cnt;
int maze[30][30];
int dir[4][2] = { { 0, -1 },{ -1, 0 },{ 0, 1 },{ 1, 0 } };
Position start;
void dfs(Position start,int step) {//step记录走了多少步for (int d = 0; d < 4; ++d) {//4个方向Position temp,temp2;temp.x = start.x + dir[d][0];temp.y = start.y + dir[d][1];if (step<cnt-1&&temp.x > 0 && temp.x <= h&&temp.y > 0 && temp.y <= w&&maze[temp.x][temp.y] !=1) {//判断冰球最初位置周围是否可走，其中step<cnt-1保证了此刻的cnt最小while (temp.x > 0 && temp.x <= h&&temp.y > 0 && temp.y <= w&&maze[temp.x][temp.y] == 0) {//如果可走，那么一直行进到遇见冰块或者出界temp.x += dir[d][0];temp.y += dir[d][1];}temp2.x = temp.x - dir[d][0];temp2.y = temp.y - dir[d][1];if (temp.x > 0 && temp.x <= h&&temp.y > 0 && temp.y <= w) {//如果是遇见了冰块，那么进行下一步搜索if (maze[temp.x][temp.y] == 3)cnt = step + 1;if (maze[temp.x][temp.y] == 1) {maze[temp.x][temp.y] = 0;//已到达，冰块消失dfs(temp2, step + 1);//搜索该位置maze[temp.x][temp.y] = 1;//维护原始数组}}}}
}
int main(void) {while(cin >> w >> h,w||h) {for (int i = 1; i <= h; ++i)for (int j = 1; j <= w; ++j) {cin >> maze[i][j];if (maze[i][j] == 2) {//整合输入，因为起点事实上在过程中也可达，故直接将起点记录且将起点设置为0start.x = i,start.y = j;maze[i][j] = 0;}}cnt = 11;dfs(start, 0);if (cnt>10)cout << -1 << endl;else cout << cnt << endl;}return 0;
}这篇关于POJ 3009 *** Curling 2.0的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
