給你一塊矩形土地的長寬,再依序給定每個機器人的初始位置狀況及一連串的指令集,你必須用你的程式求出每個機器人最後的位置狀況。
一個機器人的位置狀況包括了其坐標( x 坐標, y 坐標),和它面向的方向(用 N , S , E , W 來分別代表北、南、東、西)。至於一個機器人所收到的指令集,是一個由字母 ‘ L ‘ , ‘ R ‘ , 和 ‘ F ‘ 所構成的字串,其分別代表:
- 左轉(Left):機器人在原地往左轉 90 度。
- 右轉(Right): 機器人在原地往右轉 90 度。
- 前進(Forward): 機器人往其面向的方向向前走一格,且不改變其面向之方向。
從坐標 (x,y) 走至 (x,y+1) 的這個方向我們定義為北方。
因為此矩形土地是有邊界的,所以一旦一個機器人走出邊界掉落下去,就相當於永遠消失了。不過這個掉下去的機器人會留下「標記 ( scent ) 」,提醒以後的機器人,避免他們從同一個地方掉下去。掉下去的機器人會把標記,留在他掉落之前所在的最後一個坐標點。所以對於以後的機器人,當他正位在有標記的地方時,這個機器人就會忽略會讓他掉下去的指令。
Input
輸入裡的第一列有2個正整數,代表這個矩形世界右上角頂點的坐標,其中假設這個世界的左下角頂點坐標為 ( 0 , 0 )。
接下來是若干組有關機器人的初始位置狀況和指令集,每個機器人2列。第一列為位置狀況,包括了兩個整數和一個字元( N , S , E 或 W ),代表機器人初始的位置坐標以及機器人最初所面對的方向。第二列則是指令集,是一個由 ‘ L ‘ , ‘ R ‘ 和 ‘ F ‘ 所組成的字串。輸入以 end-of-file 作為結束。
各機器人是依序動作的,也就是說,直到一個機器人作完他全部的動作,下一個機器人才會開始動作。
所有機器人的初始位置皆會在矩形土地上,不會落在外面。任何坐標的最大值皆不會超過 50 。每個指令集的長度皆不會超過 100 個字元長。
Output
對於每一個機器人,你都必須輸出其最後所在的坐標和面對的方向。如果一個機器人會掉落出此世界外,你必須先輸出他在掉落前,最後的所在位置和面對的方向,再多加一個字: LOST 。
Sample Input
5 3 1 1 E RFRFRFRF 3 2 N FRRFLLFFRRFLL 0 3 W LLFFFLFLFL
Sample Output
1 1 E 3 3 N LOST 2 3 S
解題思考
這題步驟雖然多,但每步都很簡單,這就不詳細說明了,請觀詳以下的程式碼。
參考解答(C#)
using System; using System.Collections.Generic; //Author: kgame 許智涵 //http://kgame-blog.spaces.live.com/ namespace Q118_Mutant_Flatworld_Expolrers { class Program { /// <summary> /// 土地邊界. /// </summary> public static Point s; /// <summary> /// 死亡BOT紀錄. /// </summary> static List<Point> scent = new List<Point>(); /// <summary> /// BOT的座標. /// </summary> static Point Location; /// <summary> /// BOT的方向. /// </summary> static char V; static void Main() { string str = Console.ReadLine(); string[] strArr = str.Split(' '); s.X = int.Parse(strArr[0]); s.Y = int.Parse(strArr[1]); while ((str = Console.ReadLine()) != null) { strArr = str.Split(' '); Location.X = int.Parse(strArr[0]); Location.Y = int.Parse(strArr[1]); V = strArr[2][0]; str = Go(Console.ReadLine()); Console.WriteLine(str); } } /// <summary> /// 出發並回傳結果. /// </summary> /// <param name="acts">指令集</param> /// <returns></returns> static string Go(string acts) { foreach (char a in acts) { switch (a) { case 'L': TurnLeft(); break; case 'R': TurnRight(); break; case 'F': if (Forward()) break; return string.Format("{0} {1} {2} LOST", Location.X, Location.Y, V); } } return string.Format("{0} {1} {2}", Location.X, Location.Y, V); } static void TurnLeft() { switch (V) { case 'N': V = 'W'; break; case 'W': V = 'S'; break; case 'S': V = 'E'; break; case 'E': V = 'N'; break; } } static void TurnRight() { switch (V) { case 'N': V = 'E'; break; case 'E': V = 'S'; break; case 'S': V = 'W'; break; case 'W': V = 'N'; break; } } static bool Forward() { if ((V == 'W' && Location.X == 0) || (V == 'S' && Location.Y == 0) || (V == 'E' && Location.X == s.X) || (V == 'N' && Location.Y == s.Y)) { if (scent.Contains(Location)) return true; else { scent.Add(Location); return false; } } switch (V) { case 'N': ++Location.Y; break; case 'S': --Location.Y; break; case 'E': ++Location.X; break; case 'W': --Location.X; break; } return true; } } struct Point { public int X, Y; } }
發表留言