题目大意：就是给你一个冰壶和一个地图，地图上有石头，冰壶只能沿着x方向和y方向运动，并且要一直运动直到撞到石头为止，并且沿着此方向撞过来会把挡住的石头撞没，冰壶在停的时候可以扔出去一次，最多只能扔10次，问你冰壶能否到指定点？
这一题原题非常长，需要很细心地读题（比如我一开始的时候就是没看到只能扔10次，导致好几次tle），而且这一题一开始我还做复杂了，一开始的时候用的是dfs+dp去储存最短距离，可是我发现冰壶会撞烂石头，所以储存最短距离是不行的，所以只能直接dfs了
直接dfs的方法就是沿着一个方向，如果没有障碍物，我们就继续往下一个搜索，如果遇到障碍物，那么我们就在这个方向再沿着4个方向再搜索（如果没有石头挡着的话），遇到终点我们就更新minstep，如果扔的次数大于10次，那么就不用再搜索了，minstep初始化为11就好了
PS：这一题一开始我是256ms过的（因为我用的INT_MAX返回来标记的，非常耗时间），后来删掉了返回值，直接用step标记，速度直接快了一倍，然后还更简洁了
另外WA好几次，还是边界判断的问题，看来我还是要多注意一下
1 #include <iostream> 2 #include <algorithm> 3 4 using namespace std; 5 typedef int Direction;//0表示左，1表示右，2表示上，3表示下 6 typedef int Position; 7 8 static int w, h; 9 static int map[20][20];//0联通，1阻挡，2起点，3终点 10 static pair< int, int >start; 11 static pair< int, int >goal; 12 int minstep; 13 14 void Search(const Position, const Position, const Direction, const int); 15 void Find_Ans(Position, Position, Direction, const int); 16 void Read_Map(const int,const int); 17 18 int main(void) 19 { 20 while (~scanf("%d%d", &w, &h)) 21 { 22 if (w == 0 && h == 0) 23 break; 24 Read_Map(h, w); 25 minstep = 11; 26 for (int i = 0; i < 4; i++) 27 { 28 if (i == 0 && start.second - 1 >= 0 && map[start.first][start.second - 1] != 1) 29 Search(start.first, start.second, i, 1); 30 else if (i == 1 && start.second + 1 < w && map[start.first][start.second + 1] != 1) 31 Search(start.first, start.second, i, 1); 32 else if (i == 2 && start.first - 1 >= 0 && map[start.first - 1][start.second] != 1) 33 Search(start.first, start.second, i, 1); 34 else if (i == 3 && start.first + 1 < h && map[start.first + 1][start.second] != 1) 35 Search(start.first, start.second, i, 1); 36 } 37 if (minstep > 10) 38 cout << -1 << endl; 39 else 40 cout << minstep << endl; 41 } 42 return 0; 43 } 44 45 void Read_Map(const int h, const int w) 46 { 47 for (int y = 0; y < h; y++) 48 { 49 for (int x = 0; x < w; x++) 50 { 51 scanf("%d", &map[y][x]); 52 if (map[y][x] == 2) 53 { 54 start.first = y;//y坐标 55 start.second = x;//x坐标 56 } 57 if (map[y][x] == 3) 58 { 59 goal.first = y;//y坐标 60 goal.second = x;//x坐标 61 } 62 } 63 } 64 } 65 66 void Find_Ans(Position y, Position x, Direction dir,const int step) 67 { 68 for (int i = 0; i < 4; i++) 69 { 70 if (i == 0 && x - 1 >= 0 && map[y][x - 1] != 1) 71 Search(y, x - 1, i, step + 1); 72 else if (i == 1 && x + 1 < w && map[y][x + 1] != 1) 73 Search(y, x + 1, i, step + 1); 74 else if (i == 2 && y - 1 >= 0 && map[y - 1][x] != 1) 75 Search(y - 1, x, i, step + 1); 76 else if (i == 3 && y + 1 < h && map[y + 1][x] != 1) 77 Search(y + 1, x, i, step + 1); 78 } 79 } 80 81 void Search(const Position y, const Position x, const Direction dir,const int step) 82 { 83 if (step > minstep) 84 return; 85 if (x == goal.second && y == goal.first)//如果这个点就是正确的点,返回0步 86 { 87 minstep = min(minstep, step); 88 return; 89 } 90 if (dir == 0) 91 { 92 if (x - 1 < 0) 93 return; 94 else if (map[y][x - 1] != 1) 95 Search(y, x - 1, dir, step); 96 else 97 { 98 map[y][x - 1] = 0;//先撞烂 99 Find_Ans(y, x, dir, step); 100 map[y][x - 1] = 1;//然后补回来 101 } 102 } 103 else if (dir == 1) 104 { 105 if (x + 1 >= w) 106 return; 107 else if (map[y][x + 1] != 1) 108 Search(y, x + 1, dir, step); 109 else 110 { 111 map[y][x + 1] = 0;//先撞烂 112 Find_Ans(y, x, dir, step); 113 map[y][x + 1] = 1;//然后补回来 114 } 115 } 116 else if (dir == 2) 117 { 118 if (y - 1 < 0) 119 return; 120 else if (map[y - 1][x] != 1) 121 return Search(y - 1, x, dir, step); 122 else 123 { 124 map[y - 1][x] = 0;//先撞烂 125 Find_Ans(y, x, dir, step); 126 map[y - 1][x] = 1;//然后补回来 127 } 128 } 129 else 130 { 131 if (y + 1 >= h) 132 return; 133 else if (map[y + 1][x] != 1) 134 Search(y + 1, x, dir, step); 135 else 136 { 137 map[y + 1][x] = 0;//先撞烂 138 Find_Ans(y, x, dir, step); 139 map[y + 1][x] = 1;//然后补回来 140 } 141 } 142 }