题目大意：就是给你一个冰壶和一个地图，地图上有石头，冰壶只能沿着x方向和y方向运动，并且要一直运动直到撞到石头为止，并且沿着此方向撞过来会把挡住的石头撞没，冰壶在停的时候可以扔出去一次，最多只能扔10次，问你冰壶能否到指定点？
这一题原题非常长，需要很细心地读题（比如我一开始的时候就是没看到只能扔10次，导致好几次tle），而且这一题一开始我还做复杂了，一开始的时候用的是dfs+dp去储存最短距离，可是我发现冰壶会撞烂石头，所以储存最短距离是不行的，所以只能直接dfs了
直接dfs的方法就是沿着一个方向，如果没有障碍物，我们就继续往下一个搜索，如果遇到障碍物，那么我们就在这个方向再沿着4个方向再搜索（如果没有石头挡着的话），遇到终点我们就更新minstep，如果扔的次数大于10次，那么就不用再搜索了，minstep初始化为11就好了
PS：这一题一开始我是256ms过的（因为我用的INT_MAX返回来标记的，非常耗时间），后来删掉了返回值，直接用step标记，速度直接快了一倍，然后还更简洁了
另外WA好几次，还是边界判断的问题，看来我还是要多注意一下
#include <iostream>
#include <algorithm> using namespace std;
typedef int Direction;//0表示左，1表示右，2表示上，3表示下
typedef int Position; static int w, h;
static int map[][];//0联通，1阻挡，2起点，3终点
static pair< int, int >start;
static pair< int, int >goal;
int minstep; void Search(const Position, const Position, const Direction, const int);
void Find_Ans(Position, Position, Direction, const int);
void Read_Map(const int,const int); int main(void)
{
while (~scanf("%d%d", &w, &h))
{
if (w == && h == )
break;
Read_Map(h, w);
minstep = ;
for (int i = ; i < ; i++)
{
if (i == && start.second - >= && map[start.first][start.second - ] != )
Search(start.first, start.second, i, );
else if (i == && start.second + < w && map[start.first][start.second + ] != )
Search(start.first, start.second, i, );
else if (i == && start.first - >= && map[start.first - ][start.second] != )
Search(start.first, start.second, i, );
else if (i == && start.first + < h && map[start.first + ][start.second] != )
Search(start.first, start.second, i, );
}
if (minstep > )
cout << - << endl;
else
cout << minstep << endl;
}
return ;
} void Read_Map(const int h, const int w)
{
for (int y = ; y < h; y++)
{
for (int x = ; x < w; x++)
{
scanf("%d", &map[y][x]);
if (map[y][x] == )
{
start.first = y;//y坐标
start.second = x;//x坐标
}
if (map[y][x] == )
{
goal.first = y;//y坐标
goal.second = x;//x坐标
}
}
}
} void Find_Ans(Position y, Position x, Direction dir,const int step)
{
for (int i = ; i < ; i++)
{
if (i == && x - >= && map[y][x - ] != )
Search(y, x - , i, step + );
else if (i == && x + < w && map[y][x + ] != )
Search(y, x + , i, step + );
else if (i == && y - >= && map[y - ][x] != )
Search(y - , x, i, step + );
else if (i == && y + < h && map[y + ][x] != )
Search(y + , x, i, step + );
}
} void Search(const Position y, const Position x, const Direction dir,const int step)
{
if (step > minstep)
return;
if (x == goal.second && y == goal.first)//如果这个点就是正确的点,返回0步
{
minstep = min(minstep, step);
return;
}
if (dir == )
{
if (x - < )
return;
else if (map[y][x - ] != )
Search(y, x - , dir, step);
else
{
map[y][x - ] = ;//先撞烂
Find_Ans(y, x, dir, step);
map[y][x - ] = ;//然后补回来
}
}
else if (dir == )
{
if (x + >= w)
return;
else if (map[y][x + ] != )
Search(y, x + , dir, step);
else
{
map[y][x + ] = ;//先撞烂
Find_Ans(y, x, dir, step);
map[y][x + ] = ;//然后补回来
}
}
else if (dir == )
{
if (y - < )
return;
else if (map[y - ][x] != )
return Search(y - , x, dir, step);
else
{
map[y - ][x] = ;//先撞烂
Find_Ans(y, x, dir, step);
map[y - ][x] = ;//然后补回来
}
}
else
{
if (y + >= h)
return;
else if (map[y + ][x] != )
Search(y + , x, dir, step);
else
{
map[y + ][x] = ;//先撞烂
Find_Ans(y, x, dir, step);
map[y + ][x] = ;//然后补回来
}
}
}