Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10963 | Accepted: 4619 |
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.
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.
- The stone hits a block (Fig. 2(b), (c)).
- 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.
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).
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
题意:
给出 N 和 M,代表有 N 行 M 列(<= 20),后给出 N X M 的地图信息,1 代表障碍物,2 代表起点,3 代表终点。起点可以任意4个方向走,当碰到障碍物的时候停下,没有障碍物阻挡则不停下,并且击碎相邻的障碍物,问最少走多少步能走到终点,最多步数不超过10。
思路:
DFS。注意没有碰到障碍物是不会停下的,所以当走出地图就当作是失败,还有注意行列是调换输入的。细心。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std; const int MAX = 15; int n, m, Min, sx, sy, ex, ey; int Map[25][25]; int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1}; void dfs (int ans, int x, int y, int way) { if (ans > 10) return; while (x + dir[way][0] >= 1 && y + dir[way][1] >= 1 && x + dir[way][0] <= n && y + dir[way][1] <= m && !Map[x + dir[way][0]][y + dir[way][1]]) { x += dir[way][0]; y += dir[way][1]; if (x == ex && y == ey) { Min = min(Min, ans); return; } } if (x + dir[way][0] < 1 || y + dir[way][1] < 1 || x + dir[way][0] > n || y + dir[way][1] > m ) return; Map[x + dir[way][0]][y + dir[way][1]] = 0; for (int i = 0; i < 4; ++i) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && !Map[nx][ny]) { dfs(ans + 1, x, y, i); } } Map[x + dir[way][0]][y + dir[way][1]] = 1; } int main() { //freopen("test.in", "r", stdin); while (~scanf("%d%d", &m, &n) && (n + m)) { Min = MAX; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &Map[i][j]); if (Map[i][j] == 2) { sx = i; sy = j; } else if (Map[i][j] == 3) { ex = i; ey = j; } } } Map[sx][sy] = Map[ex][ey] = 0; for (int i = 0; i < 4; ++i) { int nx = sx + dir[i][0]; int ny = sy + dir[i][1]; if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && !Map[nx][ny]) { dfs(1, sx, sy, i); } } if (Min != MAX) printf("%d\n", Min); else printf("-1\n"); } return 0; }
相关推荐
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
八百多张冰壶训练数据集训练完成的权重模型,测试过可直接使用。在CPU为i7 9700k和显卡1050Ti以及16G内存的环境下,帧率可达到60+,准确率也超过90%
Adnroid curling effect to reader or html shower.
实现智能冰壶的自主决策,同时根据规则判定是否进入不可冲撞区
此示例中突出显示的功能: - 使用 Stateflow for MATLAB 定义使用 App Designer 创建的应用程序的逻辑- 如何从 MATLAB Stateflow 图仿真 Simulink 模型- 如何从正在运行的 Simulink 模型为 MATLAB 应用程序设置动画...
OpenRock Curling是一款具有网络支持的免费冰壶游戏。 它是用Java编写的,并且应在JRE 6或更高版本的所有平台上运行。
新的时空概念和氖壳中的时空维卷曲机制,许昆明,,传统的欧氏几何无法准确地描述电子在原子中的运动状态,即使是最简单的氢原子中的一个电子,采用薛定鄂方程求解也是很烦琐的事。
curling_stats
matlab开发-TheCurlingGame。模拟单端卷曲的应用程序
这是我第一次使用github!
冰壶Google App Script项目可安排和跟踪冰壶联赛
M-TEST, an electrostatic pull-in approach for the in-situ mechanical property measure- ments of microelectromechanical systems (MEMS), is ...supports, and curling in cantilevers due to stress-gradients.
The book is written for database administrators who need to get work done and lack the luxury of curling up fireside with a stack of operating-system documentation. What this book provides instead is...
the book is written for database administrators who need to get work done and lack the luxury of curling up fireside with a stack of Linux documentation. The book is task–oriented: Look up the task ...
The book is written for database administrators who need to get work done and lack the luxury of curling up fireside with a stack of operating-system documentation. What this book provides instead is...
有时它们甚至比 CURLing API 本身更难使用。 我们已经构建了这个包来帮助你发生这种情况。 ###快速开始 在开始之前,您需要安装 Restinga 作为项目依赖项。 你可以通过运行来做到这一点: 作曲家需要代码广播/...
贝岭的matlab的代码THP 最终项目 ...:curling_stone: :middle_finger: :panda: :Argentina: 技术规格 Ruby v 2.5.1 关键宝石:AWS 主动存储、Stripe、Mailchimp (Gibbon)、字体真棒...... 列表模板
To address these issues, tin-phosphorus-oxygen (SnPO).composite materials were protected by the curling of reduced graphene oxide (rGO) induced by the.fluorine atoms from the electrolyte. The in-situ...
rem rem $Header: summit2.sql 27-jun-2000.12:30:22 slari Exp $ rem ... All rights reserved. rem rem NAME rem summit2.sql - rem DESCRIPTION rem rem RETURNS ...rem Create and populate tables and sequences to...