---
title: 'UVa 118 題解 — C++'
disqus: hackmd
---

# UVa 118 題解 — C++
:::info
:bulb: 此筆記為UVa 118的題目詳解，包含解題思路、C++範例程式碼。
:::

## Mutant Flatworld Expolrers (ZeroJudge c082.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=c082)
:::success
給你一塊矩形土地的長寬，再依序給定每個機器人的初始位置狀況及一連串的指令集，你必須用你的程式求出每個機器人最後的位置狀況。

一個機器人的位置狀況包括了其坐標（ x 坐標， y 坐標），和它面向的方向（用 N , S , E , W 來分別代表北、南、東、西）。至於一個機器人所收到的指令集，是一個由字母 ' L ' ， ' R ' ， 和 ' F ' 所構成的字串，其分別代表：

* 左轉（Left）：機器人在原地往左轉 90 度。
* 右轉（Right）: 機器人在原地往右轉 90 度。
* 前進（Forward）: 機器人往其面向的方向向前走一格，且不改變其面向之方向。
從坐標 (x,y) 走至 (x,y+1) 的這個方向我們定義為北方。

因為此矩形土地是有邊界的，所以一旦一個機器人走出邊界掉落下去，就相當於永遠消失了。不過這個掉下去的機器人會留下「標記 ( scent ) 」，提醒以後的機器人，避免他們從同一個地方掉下去。掉下去的機器人會把標記，留在他掉落之前所在的最後一個坐標點。所以對於以後的機器人，當他正位在有標記的地方時，這個機器人就會忽略會讓他掉下去的指令。
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
我透過 x、y 紀錄機器人所在的位置、dir 紀錄朝向方向，並比對 dir 與 moved 陣列中的字元，若相同則將 d 設置為該索引值。

我設定 moved[4]={'N','E','S','W'}; ，當指令為 R 時，只需將 $d + 1$ 即可，但當 d + 1 > 3 時，則需將 d 設為 0，因此我利用 d = (d + 1) % 4; 實現；當指令為 L 時，只需將 $d - 1$ 即可，但當 d - 1 = 0 時，則需將 d 設為 3。

此外我設定 move 陣列確定移動方向與朝向的關係，當指令為 F 時，則令 nx、ny 加上指定數值，並依以下規則判斷：
1. 若 nx、ny 超出邊界（掉出世界外） **且** 該位置尚未被標記 => 輸出答案並標記該位置
2. 若 nx、ny 在邊界內 => 將 x、y 更新為 nx、ny
3. 其餘狀況 => 忽略
:::

### 範例程式碼

#include <bits/stdc++.h>
using namespace std;

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j;
	int n, m;
	
	cin >> n >> m;
	
	int map[n+2][m+2]={};
	int x, y, d, nx, ny, lost;
	char dir;
	string c;
	char moved[4]={'N','E','S','W'};
	int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
	
	while (cin >> x >> y >> dir >> c) {
		
		lost = 0;
		
		for (i=0;i<4;i++)
			if (dir == moved[i])
				d = i;
				
		for (i=0;i<c.size();i++) {
			if (c[i] == 'F') {
				nx = x + move[d][0];
				ny = y + move[d][1];
				
				if ((nx < 0 || nx > n || ny < 0 || ny > m) && map[x][y] != 1) {
					cout << x << " " << y << " " << moved[d] << " LOST" << endl;
					map[x][y] = 1;
					lost = 1;
					break;
				}
				else if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {
					x = nx;
					y = ny;
				}
			}
			else if (c[i] == 'R')
				d = (d + 1) % 4;
			else {
				d--;
				if (d == -1)
					d = 3;
			}
		}
		
		if (lost == 0)
			cout << x << " " << y << " " << moved[d] << endl;
	}

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (2ms, 336KB)

###### tags: `CPE 1星`

:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::