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)
blank

相关推荐

  • android 点餐系统 构思

    android 点餐系统 构思一.          为什么要做这个项目? 记的有一次看新闻,其中报道过台湾一家酒店使用ipad让客人自己点餐,客人可以使用这个ipad从全部菜中挑选自己喜欢的,又可以选择自己的特色的。还可以直接结帐。我就想了一下,为什么不在android 系统上做一个人呢,因为以后这个系统的普及度一定很高的。于是我就上网查了一下相关的项目。发现有好多人已经开始做了,我自己并没有调研,就附上别人调研的情

  • ASP.NET跳转网页的三种方法的比较(转+修)

    ASP.NET跳转网页的三种方法的比较(转+修)方法1response.redirect这个跳转页面的方法跳转的速度不快,因为它要走2个来回(2次postback),但他可以跳转到任何页面,没有站点页面限制(即可以由雅虎跳到新浪),同时不能跳过登录保护。但速度慢是其最大缺陷!redirect跳转机制:首先是发送一个http请求到客户端,通知需要跳转到新页面,然后客户端在发送跳转请求到服务器端。需要注意的是跳转后内部空间保存的所…

  • 云硬盘

    云硬盘

  • 进程间通信和线程间通信的几种方式是_线程通信方式

    进程间通信和线程间通信的几种方式是_线程通信方式进程和线程的区别:对于进程来说,子进程是父进程的复制品,从父进程那里获得父进程的数据空间,堆和栈的复制品。而线程,相对于进程而言,是一个更加接近于执行体的概念,可以和同进程的其他线程之间直接共享数据,而且拥有自己的栈空间,拥有独立序列。共同点:它们都能提高程序的并发度,提高程序运行效率和响应时间。线程和进程在使用上各有优缺点。线程执行开销比较小,但不利于资源的管理和保护,而进程相反…

  • Integer包装类_entityframework面试题

    Integer包装类_entityframework面试题Integer 包装类面试

  • java中什么是引用[通俗易懂]

    如果一个变量的类型是类类型,而非基本类型,那么该变量又叫做引用。从JDK1.2版本开始,把对象的引用分为四种级别,从而使程序能更加灵活的控制对象的生命周期。这四种级别由高到低依次为:强引用、软引用、弱引用和虚引用。

发表回复

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

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