[Java] UVa 118 Mutant Flatworld Explorers

題目連結

題意:
一個長方形網格，座標左下為(0, 0)，右上為(x, y)
有好幾隻機器人，對應題目好幾組指令

每組先給定機器人的原始座標(rx, ry)與面向方位(北N 東E 南S 西W)
接著一連串的指令，包含:
R-向右轉
L-向左轉
F-向前走，不轉向

如果機器人因為向前走超出邊界
要輸出最後所在座標、方位與"LOST"並停止該次動作
否則輸出所有指令跑完後的最後所在座標、方位

同一個測資當中，若前次機器人在某個座標LOST
會存在記憶點，也就是之後的機器人在相同位置
如果即將LOST，可以免於一死

舉例來說，假設 3*3的方格

有連續2組測資如下:
1 3 E
FFFFF
2 3 E
FFFFF

第一個機器人座標 (1, 3)，面向東方
指令FFF...，走到 3 3 E後再執行 F 發生 LOST，所以輸出 3 3 E LOST

第二個機器人座標 (2, 3)，面向東方
指令FFF...，走到 3 3 E後再執行 F 本來發生 LOST
因為有記憶點，所以可以忽略該F，繼續後續指令
最後輸出 3 3 E (因本例都是F，最後都忽略)

解法:
看似方位又一堆規則顯得複雜
其實照著題意模擬即可
唯一要注意的就是記憶點問題

模擬要記錄三個要素，機器人的x y座標(rx ry)和方位
指令L R只要改變方位
指令F就按照當下方位對座標加減:

N ry++
S ry--
E rx++
W rx--

記憶點的話，建立座標對應的布林陣列
當機器人即將發生LOST，註記當下座標
之後遇到LOST但有註記的座標就忽略

題目看起來只有一組測資
也就是同一個 x * y 網格，多個機器人

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	String nwse = "NWSE";
	String s[] = sc.nextLine().split(" ");
	int x = Integer.valueOf(s[0]);
	int y = Integer.valueOf(s[1]);
	boolean scent[][] = new boolean[x+1][y+1];
	while (sc.hasNext()) {
	boolean lost = false;
	String s2[] = sc.nextLine().split(" ");
	int rx = Integer.valueOf(s2[0]);
	int ry = Integer.valueOf(s2[1]);
	int dir = Integer.valueOf(nwse.indexOf(s2[2]));
	String ins = sc.nextLine();
	for (int i = 0; i < ins.length() && !lost; i++) {
	switch(ins.charAt(i)) {
	case 'R':
	dir = (dir-1 < 0) ? 3 : (dir-1);
	break;
	case 'L':
	dir = (dir+1 > 3) ? 0 : (dir+1);
	break;
	case 'F':
	if (dir == 0) { //N
	if ((ry+1 > y) && !scent[rx][ry]) {
	scent[rx][ry] = true;
	System.out.println(rx + " " + ry + " " + nwse.charAt(dir) + " LOST");
	lost = true;
	}
	else
	ry = (ry == y) ? ry : ry+1;
	}
	else if (dir == 1) { //W
	if ((rx == 0) && !scent[rx][ry]) {
	scent[rx][ry] = true;
	System.out.println(rx + " " + ry + " " + nwse.charAt(dir) + " LOST");
	lost = true;
	}
	else
	rx = (rx == 0) ? rx : rx-1;
	}
	else if (dir == 2) { //S
	if ((ry == 0) && !scent[rx][ry]) {
	scent[rx][ry] = true;
	System.out.println(rx + " " + ry + " " + nwse.charAt(dir) + " LOST");
	lost = true;
	}
	else
	ry = (ry == 0) ? ry : ry-1;
	}
	else //E
	if ((rx+1 > x) && !scent[rx][ry]) {
	scent[rx][ry] = true;
	System.out.println(rx + " " + ry + " " + nwse.charAt(dir) + " LOST");
	lost = true;
	}
	else
	rx = (rx == x) ? rx : rx+1;
	break;
	}
	if (i == ins.length()-1)
	System.out.println(rx + " " + ry + " " + nwse.charAt(dir));
	}
	}
	}
	}

view raw UVa118.java hosted with ❤ by GitHub