Curling 2.0(dfs)
程序员文章站
2022-04-02 23:40:12
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 rest ......
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.
-
The stone hits a block (Fig. 2(b), (c)).
which means小球每次只能在一个方向滑动,直到他撞墙(墙会消失),如果小球滑出了界外,就不继续考虑这个方向,从小球滑之前的位置遍历别的方向
#include <iostream> #define maxn 401 using 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; }
以上
推荐阅读
-
vue1.0和vue2.0的watch监听事件写法详解
-
解决Vue2.0 watch对象属性变化监听不到的问题
-
Vue2.0实现组件之间数据交互和通信操作示例
-
使用 Spring Boot 2.0 + WebFlux 实现 RESTful API功能
-
spring boot2.0实现优雅停机的方法
-
[视频]Apple Watch运行watchOS 2.0系统新功能把玩
-
vue2.0$nextTick监听数据渲染完成之后的回调函数方法
-
vue2.0 使用element-ui里的upload组件实现图片预览效果方法
-
Vue2.0+Vux搭建一个完整的移动webApp项目的示例
-
Yii2.0建立公共方法简单示例