Curling 2.0(Accept rate:40%)
Time Limit: 1000MS
Memory Limit: 65536K
http://poj.org/problem?id=3009
解答思路：
使用深度优先搜索。
有几个要注意的地方：
- 对应方向有方块(block)是不能向那个方向移动的。
- 如果当前位置与目标位置共线，如果能往那个方向移动（满足1），则一直向着那个方向即可。其结果是当前最优的。
- 与方块相撞时位置应该在方块前面一格。如果某个方向一直都没有方块，就删去该分支。
- 当移动次数超过10，就没有必要再展开分支了（题目说了大于10则输出-1），删去分支可以节省运行时间。
- 由于频繁地读取地图信息，使用全局变量来存储地图是最好的。
解答代码如下：
memory: 192K
time: 172ms
#include <iostream>
using namespace std;
int w, h; //2<=w<=20,1<=h<=20
int w_s = -1, h_s = -1; //起始坐标start
int w_g = -1, h_g = -1; //目标坐标goal
short map[21][21]; //地图
short dfs(short map[][21], int w_now, int h_now, short times)
{
//超过10次退出
if(times > 10)
return 20;
short time_now = 20;
//若当前位置与目标同列,则尝试直接向目标迈进
if(w_now == w_g)
{
//如果向上可以到达终点
if((h_now > h_g)&&(h_now - 1 > 0)&&(!map[h_now - 1][w_now]))
{
short counts = 1;//至少需要移动一次,每有一个方块阻碍则额外+1次
for (int i = 2; i < h_now - h_g;i++)
{
if(map[h_now - i][w_now])
counts++;
}
return times + counts;
}
//如果向下可以到达终点
else if((h_now < h_g)&&(h_now + 1 <= h)&&(!map[h_now + 1][w_now]))//如果沿这个方向可以到达终点
{
short counts = 1;//至少需要移动一次,每有一个方块阻碍则额外+1次
for (int i = 2; i < h_g - h_now;i++)
{
if(map[h_now + i][w_now])
counts++;
}
return times + counts;
}
}
//当前位置与目标同行，则尝试直接向目标迈进
else if(h_now == h_g)
{
//如果左移可以到达终点
if((w_now > w_g)&&(w_now - 1 > 0)&&(!map[h_now][w_now - 1]))
{
short counts = 1;//至少需要移动一次,每有一个方块阻碍则额外+1次
for (int j = 2; j < w_now - w_g;j++)
{
if(map[h_now][w_now - j])
counts++;
}
return times + counts;
}
//如果右移可以到达终点
else if((w_now < w_g)&&(w_now + 1 <= w)&&(!map[h_now][w_now + 1]))
{
short counts = 1;//至少需要移动一次,每有一个方块阻碍则额外+1次
for (int j = 2; j < w_g - w_now;j++)
{
if(map[h_now][w_now + j])
counts++;
}
return times + counts;
}
}
//上移
if((h_now - 1 > 0)&&(!map[h_now - 1][w_now]))
{
//正常沿这个方向移动，碰到砖块后停下
int up = h_now - 2;
while((up > 0)&&(!map[up][w_now]))
up--;
if((up > 0)&&(map[up][w_now]))
{
map[up][w_now] = 0;//砖块消失
time_now = min(time_now, dfs(map, w_now, up + 1,times + 1));//更新位置
map[up][w_now] = 1;//砖块复原
}
}
//下移
if((h_now + 1 < h)&&(!map[h_now + 1][w_now]))
{
//正常沿这个方向移动，碰到砖块后停下
int down = h_now + 2;
while((down <= h)&&(!map[down][w_now]))
down++;
if((down <= h)&&(map[down][w_now]))
{
map[down][w_now] = 0;//砖块消失
time_now = min(time_now, dfs(map, w_now, down - 1, times + 1)); //更新位置
map[down][w_now] = 1;//砖块复原
}
}
//左移
if((w_now - 1 > 0)&&(!map[h_now][w_now - 1]))
{
//正常沿这个方向移动，碰到砖块后停下
int left = w_now - 2;
while((left > 0)&&(!map[h_now][left]))
left--;
if((left > 0)&&(map[h_now][left]))
{
map[h_now][left] = 0;//砖块消失
time_now = min(time_now, dfs(map, left + 1, h_now, times + 1));//更新位置
map[h_now][left] = 1;//砖块复原
}
}
//右移
if((w_now + 1 < w)&&(!map[h_now][w_now + 1]))
{
//正常沿这个方向移动，碰到砖块后停下
int right = w_now + 2;
while((right <= w)&&(!map[h_now][right]))
right++;
if((right <= w)&&(map[h_now][right]))
{
map[h_now][right] = 0;//砖块消失
time_now = min(time_now, dfs(map, right - 1, h_now, times + 1));//更新位置
map[h_now][right] = 1;//砖块复原
}
}
return time_now;//输出当前最小次数
}
int main()
{
short tmp; //临时变量
cin >> w >> h;
while((w!=0)&&(h!=0))
{
short times = 0;
for (int i = 1; i <= h;i++)
{
for (int j = 1; j <= w;j++)
{
cin >> tmp;
//起点处理
if(tmp==2)
{
w_s = j;
h_s = i;
map[i][j] = 0;
}
//终点处理
else if(tmp==3)
{
w_g = j;
h_g = i;
map[i][j] = 0;
}
//其他点处理
else
{
map[i][j] = tmp;
}
}
}
//开始深度搜索
times = dfs(map, w_s, h_s, times);
if(times > 10)
cout << -1 << endl;
else
cout << times << endl;
cin >> w >> h;
}
return 0;
}
