POJ 3009-Curling 2.0(DFS)

POJ 3009-Curling 2.0(DFS)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Curling 2.0
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 12158   Accepted: 5125

Description

On Planet MM-21, after their Olympic games this year, curling is getting popular. But the rules are somewhat different from ours. The game is played on an ice game board on which a square mesh is marked. They use only a single stone. The purpose of the game is to lead the stone from the start to the goal with the minimum number of moves.

Fig. 1 shows an example of a game board. Some squares may be occupied with blocks. There are two special squares namely the start and the goal, which are not occupied with blocks. (These two squares are distinct.) Once the stone begins to move, it will proceed until it hits a block. In order to bring the stone to the goal, you may have to stop the stone by hitting it against a block, and throw again.

POJ 3009-Curling 2.0(DFS)
Fig. 1: Example of board (S: start, G: goal)

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:
    • 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.
  • 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.

POJ 3009-Curling 2.0(DFS)
Fig. 2: Stone movements

Under the rules, we would like to know whether the stone at the start can reach the goal and, if yes, the minimum number of moves required.

With the initial configuration shown in Fig. 1, 4 moves are required to bring the stone from the start to the goal. The route is shown in Fig. 3(a). Notice when the stone reaches the goal, the board configuration has changed as in Fig. 3(b).

POJ 3009-Curling 2.0(DFS)
Fig. 3: The solution for Fig. D-1 and the final board configuration

Input

The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. The number of datasets never exceeds 100.

Each dataset is formatted as follows.

the width(=w) and the height(=h) of the board 
First row of the board
 
… 
h-th row of the board

The width and the height of the board satisfy: 2 <= w <= 20, 1 <= h <= 20.

Each line consists of w decimal numbers delimited by a space. The number describes the status of the corresponding square.

0 vacant square
1 block
2 start position
3 goal position

The dataset for Fig. D-1 is as follows:

6 6 
1 0 0 2 1 0 
1 1 0 0 0 0 
0 0 0 0 0 3 
0 0 0 0 0 0 
1 0 0 0 0 1 
0 1 1 1 1 1

Output

For each dataset, print a line having a decimal integer indicating the minimum number of moves along a route from the start to the goal. If there are no such routes, print -1 instead. Each line should not have any character other than this number.

Sample Input

2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3
0 0

Sample Output

1
4
-1
4
10
-1
写到吐啊有木有。。
题意: 给一张地图。2为起点,3为终点,有一个冰壶,从起点開始滑行。碰到石头(1)停止,这样算1步。越界算失败,问滑到终点最少多少步。到不了终点输出-1;
然后DFS就能够了。

。。悲剧的是地图要初始化。不然会wa到死。

。尽管如今还是不明确地图为什么非要初始化,可能是搜索过程中开全局变量会变异?

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 116
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ?

(x) : (y) )#define min(x,y) ( ((x) > (y)) ?

(y) : (x) )using namespace std;int n, m, ans, sx, sy;int ma[24][24];int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, { -1, 0}};void dfs(int x, int y, int step){ if (step >= 10) { return ; } if (step >= ans) { return ; } for (int i = 0; i < 4; i++) { int tx = dir[i][0] + x; int ty = dir[i][1] + y; if (tx >= 1 && tx <= m && ty >= 1 && ty <= n && ma[tx][ty] != 1) { while (tx >= 1 && ty >= 1 && tx <= m && ty <= n && ma[tx][ty] != 1 && ma[tx][ty] != 3) { tx += dir[i][0]; ty += dir[i][1]; } if ((tx == 1 || ty == 1 || tx == m || ty == n) && ma[tx][ty] == 0) { continue; } if (ma[tx][ty] == 3) { ans = min(ans, step + 1); return ; } if (ma[tx][ty] == 1) { ma[tx][ty] = 0; dfs(tx - dir[i][0], ty - dir[i][1], step + 1); ma[tx][ty] = 1; } } }}int main(){ while (scanf("%d %d", &n, &m) != EOF) { if (!n && !m) { break; } memset(ma, 0, sizeof(ma)); for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { scanf("%d", &ma[i][j]); if (ma[i][j] == 2) { sx = i; sy = j; } } ans = INF; dfs(sx, sy, 0); if (ans != INF) { printf("%d\n", ans); } else { puts("-1"); } } return 0;}

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117032.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • tracert原理及其实现_tracert第一个地址是什么

    tracert原理及其实现_tracert第一个地址是什么Tracert用于测试数据包从发送主机到目的地所经过的网关,它主要用于检查网络连接是否可达,以及分析网络什么地方发生了故障.Tracert的执行过程是:首先发送一个TTL为1的数据包,因此第一跳发送回一个ICMP错误消息以指明此数据包不能被发送(因为TTL超时)之后此数据包被重新发送,TTL为2,同样第二跳返回TTL超时,这个过程不断进行,直到到达目的地.执行这些过程的目的是记录每一个ICM

  • iptables命令 高级网络

    iptables命令 高级网络

    2021年10月14日
  • 延时1s的延时子程序_用一个时间常数为0.35秒的一阶装置

    延时1s的延时子程序_用一个时间常数为0.35秒的一阶装置文档介绍:目录第一部分设计任务及方案1、设计题目及要求2、设计方案分析论证第二部分方案各模块分析1、被控对象分析2、测量元件热电阻及前置放大电路3、A/D转换器4、控制器(单片机)5、光隔驱动器第三部分数字控制器D(Z)的设计1、数字控制器D(Z)2、程序流程图设计第四部分可靠性和抗干扰性的分析第五部分心得体会设计任务及方案1.1设计题目及要求1、针对一个具有大纯时延时间的一阶惯性环节()温度控…

  • 进销存软件开发视频教程(C#版,共70讲)

    进销存软件开发视频教程(C#版,共70讲)课程出处:学途无忧网课程观看地址:http://www.xuetuwuyou.com/course/28  本教程以进销存管理实务为基础,采用时下主流的开发工具(VisualStudio2008+SQLServer2005),使用流行的C#语言。涵盖软件开发的全部过程,包括需求分析、数据库设计、架构设计、程序编码、软件发布。讲解以深入浅出为主,同时循序渐进。对软件开发过

  • STM32CubeMX实战教程(三)——外部中断(中断及HAL_Delay函数避坑)

    STM32CubeMX实战教程(三)——外部中断(中断及HAL_Delay函数避坑)前言学单片机的,相信对中断的概念都已经了如指掌了,中断具体是什么我在这里也就不再详细说明,不懂的上网找找也一大堆。那么在介绍实验之前我先跟大家简单讲讲STM32当中的NVIC(嵌套向量中断控制器)NVICNVIC(嵌套向量中断控制器)。NVIC就是控制中断响应的。主要由三个参数,一个是中断使能,一个是抢占优先级,还有一个就是响应优先级。(优先级数值越小,优先级别越高)中断使能很好理解,就是…

  • Java中&、|、&&、||详解

    Java中&、|、&&、||详解1、Java中&amp;叫做按位与,&amp;&amp;叫做短路与,它们的区别是:&amp;既是位运算符又是逻辑运算符,&amp;的两侧可以是int,也可以是boolean表达式,当&amp;两侧是int时,要先把运算符两侧的数转化为二进制数再进行运算,而短路与(&amp;&amp;)的两侧要求必须是布尔表达式。举例如下:12&amp;5的值是多少?答:12转成二进制数是1100(前四…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号