Curling 2.0(dfs)

发布时间：2023-09-06 01:59责任编辑：傅花花关键词：url

The movement of the stone obeys the following rules:

At the beginning, the stone stands still at the start square.
The movements of the stone are restricted to x and y directions. Diagonal moves are prohibited.
When the stone stands still, you can make it moving by throwing it. You may throw it to any direction unless it is blocked immediately(Fig. 2(a)).
Once thrown, the stone keeps moving to the same direction until one of the following occurs:You cannot throw the stone more than 10 times in a game. If the stone does not reach the goal in 10 moves, the game ends in failure.
- The stone hits a block (Fig. 2(b), (c)).
  - The stone stops at the square next to the block it hit.
  - The block disappears.
- The stone gets out of the board.
  - The game ends in failure.
- The stone reaches the goal square.
  - The stone stops there and the game ends in success.

which means小球每次只能在一个方向滑动，直到他撞墙（墙会消失），如果小球滑出了界外，就不继续考虑这个方向，从小球滑之前的位置遍历别的方向

#include <iostream>#define maxn 401using namespace std;int w, h, min;int cell[maxn][maxn];const int INF= 9999999;struct direction{//方向数组 ???int r, c;}dir[4] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };bool check(int nowh, int noww)//出界，fail{ ???if (nowh < 0 || noww < 0 || nowh >= h || noww >= w){ ???????return false; ???} ???return true;}void dfs(int nowi, int nowj, int step){ ???step++;//attention!!!每次进入搜索步数都要++ ???if (step > 10){//搜索超过10次就输了 ???????return;//返回主函数 ???} ???for (int i = 0; i < 4; i++){ ???????int nexti = dir[i].r + nowi; ???????int nextj = dir[i].c + nowj; ???????int flag = 0;//flag放在这里惹 ???????if (cell[nexti][nextj] == 1||check(nexti,nextj)==false){//是墙或者越界的地方不用进行搜索 ???????????continue; ???????} ???????//以下是搜索 ???????while (cell[nexti][nextj] != 1 && cell[nexti][nextj] != 3){ ???????????nexti += dir[i].r; ???????????nextj += dir[i].c; ???????????if (check(nexti, nextj) == false){//越界了 ???????????????flag = 1; ???????????????break; ???????????} ???????} ???????if (flag){//此方向不可走 ???????????continue; ???????} ???????if (cell[nexti][nextj] == 3){ ???????????if (step < min){ ???????????????min = step; ???????????} ???????????continue;//继续寻找别的路径 ???????} ???????//cell是0或2，因为起点没改为0 ???????cell[nexti][nextj] = 0; ???????dfs(nexti - dir[i].r, nextj - dir[i].c, step);//坑爹，步数在这里加1就错 ???????cell[nexti][nextj] = 1; ???}}int main(){#ifdef local ???freopen("input.txt", "r", stdin);#endif // local ???int si, sj; ???while (cin >> w >> h&&w != 0 && h != 0){ ???????for (int i = 0; i < h; i++){ ???????????for (int j = 0; j < w; j++){ ???????????????cin >> cell[i][j]; ???????????????if (cell[i][j] == 2){ ???????????????????si = i; ???????????????????sj = j; ???????????????} ???????????} ???????} ???????min = INF; ???????dfs(si, sj, 0); ???????if (min != INF){ ???????????cout << min << endl; ???????} ???????else{ ???????????cout << -1 << endl; ???????} ???} ???return 0;}

以上

Curling 2.0(dfs)

原文地址：https://www.cnblogs.com/newdawnfades/p/9158755.html

Curling 2.0(dfs)

知识推荐