Koios1143的筆記

UVa 118

發表於 分類於

UVa 118

題目

http://domen111.github.io/UVa-Easy-Viewer/?118

有幾個機器人在 $x \times y$ 大小的地圖裡移動

移動方式包含 左轉 右轉 前進

當機器人走出地圖邊界，就會掉下去，並且在最後經過的點坐下標記

當其他機器人下次要走出地圖邊界，並且看到這個標記時，會自動忽略掉下去的指令

現在針對每一個機器人，詢問移動結束後的座標位置

想法

直接將整個過程模擬過一遍

記得除了記錄現在在哪裡之外，也要記錄當前面向哪個方向

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
using namespace std;
int n,m,sx,sy,face,arr[55][55];
char c,dir[4]={'N','E','S','W'};
string op;
int get_face(char ch){
	if(ch=='N') return 0;
	else if(ch=='E') return 1;
	else if(ch=='S') return 2;
	return 3;
}
int main(){
	cin>>n>>m;
	while(cin>>sx>>sy>>c){
		// 以數字表示方位
		face=get_face(c);
		cin>>op;
		bool lost=false;
		// 針對指令進行操作
		for(int i=0 ; i<op.size() ; i++){
			if(op[i]=='L'){
				face--;
				if(face<0) face=3;
			}
			else if(op[i]=='R'){
				face++;
				if(face>3) face=0;
			}
			else{
				if(face==0){
					if(sy+1>m){
						if(arr[sx][sy]==0){
							arr[sx][sy]=-1;
							lost=true;
							break;
						}
					}
					else
						sy++;
				}
				else if(face==1){
					if(sx+1>n){
						if(arr[sx][sy]==0){
							arr[sx][sy]=-1;
							lost=true;
							break;
						}
					}
					else
						sx++;
				}
				else if(face==2){
					if(sy-1<0){
						if(arr[sx][sy]==0){
							arr[sx][sy]=-1;
							lost=true;
							break;
						}
					}
					else
						sy--;
				}
				else if(face==3){
					if(sx-1<0){
						if(arr[sx][sy]==0){
							arr[sx][sy]=-1;
							lost=true;
							break;
						}
					}
					else
						sx--;
				}
			}
		}
		cout<<sx<<" "<<sy<<" "<<dir[face];
		if(lost){
			cout<<" LOST\n";
		}
		else{
			cout<<'\n';
		}
	}
	return 0;
}

時間複雜度分析

對於每一個指令操作的時間複雜度為 $O(1)$

操作每個機器人的時間複雜度為 $O(len(op))$