当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1927:Lemmings, Lemmings Everywhere. But Not For Long.

题目描述
On an n * m board there is a lemming on each square. Every second, the lemmings try to move either north, south, east or west, according to rules which are explained below. To determine which direction to move in, each lemming has an agenda, which is an ordering of the four possible directions (for example, one possible agenda might be NWES). The rules for lemming movement are the following:
1. Initially each lemming sets its direction of movement D to the first direction in its agenda.
2. At each time step, each lemming tries to move in its direction D. Three things can happen to lemming L:
(a) If L's current direction D causes it to move off the board, then the world has one less lemming in it. Otherwise, L's target destination will be to another square.
(b) If L's target square is empty or about to become empty as a result of another lemming leaving it, and no other lemming wants to move to the same square, then L moves into its target square. In this case, the lemming will use the same direction D in the next time step.
(c) Otherwise, if another lemming is trying to move into L's target square, or if the target square contains a lemming which cannot move, then L stays put. In this case, it will update its D by going to the next direction in its agenda (wrapping around to the beginning if necessary).
Two lemmings which want to exchange squares can do so, unless of course some other lemming is trying to move into one of their two squares (in which case all three of the lemmings would stay in their current squares). Lemmings being lemmings, they continue to move until all of them have moved off the board.
Your job is to determine how long that takes.
输入解释
Input will consist of multiple test cases. Each test case will consist of multiple lines. The first line will contain two positive integers n m, specifying the number of rows and columns in the board. The maximum value for each of these is 100. The board is situated so that square (0, 0) is in the southwest corner, and square (0,m -1) is in the southeast corner. Following this will be several rows containing the agendas for the nm lemmings. Each agenda will be a permutation of the string NESW. There will be 16 agendas on each line (except perhaps the last), with a single space between each. The agendas are assigned row-wise to the lemmings, so that the first agenda is associated with the lemming on square (0, 0), the second with the lemming on square (0, 1), and so on. The last case will be followed by the line 0 0 which will terminate input.
输出解释
For each test case, output a single line containing the case number (using the format shown below) followed by the number of steps it takes until the last lemming(s) falls off the board. Use only single spaces to separate items on a line.
输入样例
2 2
ENWS WSNE NESW WENS
2 2
ENWS WSNE NESW SWEN
0 0
输出样例
Case 1: 2
Case 2: 3
来自杭电HDUOJ的附加信息
Recommend 威士忌

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-1927

最后修改于 2020-10-25T22:48:57+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/1000MS(Java/Others) 32768/32768K(Java/Others)