Koios1143的筆記

UVa 10047

發表於 分類於

UVa 10047

題解

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

有一個輪子，從圓心將輪子平分成五等分，每等分都是 $72^{\circ}$，並且都有一個顏色，如附圖

一開始這個輪子都是以綠色觸碰地面

在一張地圖上有起點、終點、障礙物，現在輪子在起點朝向北方，每次你可以選擇要 前進、右轉$90^{\circ}$、左轉$90^{\circ}$

每次前進，輪子就會以下一個顏色觸碰地面

請問，走到終點並且以綠色觸碰地面的最少操作數是多少

想法

因為要找的是最少操作數，可以想到用 BFS

因為除了走到終點以外，還需要符合綠色觸碰地面的條件，所以我們可以以 不同的方向、不同顏色觸碰地面 去走過走過的點

所以對於每個點的狀態有

  • X 座標
  • Y 座標
  • 方向
  • 顏色

接下來分別對三個不的同操作來轉移，記錄下 操作次數、拜訪與否 即可

這題跟過去 BFS 不太一樣的是，之前的題目大概都是只拿座標當作狀態，但是在本題多了方向、顏色的因素

計算操作次數也是一樣，如果只拿座標去當作參數，那會造成不同的狀態共用一個操作次數，這樣是不合理的

我自己寫這題的時候就沒考慮到這些，然後被卡了很久w

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
//By Koios1143
#include<iostream>
using namespace std;
// 0: N, 1: W, 2: S, 3: E
// 0: Green, 1: Black, 2: Red, 3: Blue, 4: White
int n, m, x, y, start_x, start_y, end_x, end_y, dir, color, nx, ny, ncolor, ndir, ans, Case=1;
int dis[30][30][4][5], que[2000000][4];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
int co[] = {1, 0, 0};
int dd[] = {0, 1, 3};
const int MaxN = 2147483647;
char arr[30][30];
bool vis[30][30][4][5];

int BFS(){
	que[0][0] = start_x;
	que[0][1] = start_y;
	que[0][2] = 0;
	que[0][3] = 0;
	vis[start_x][start_y][0][0] = true;
	dis[start_x][start_y][0][0] = 0;
	
	for(int i=0, j=1 ; i<j ; i++){
		x = que[i][0];
		y = que[i][1];
		dir = que[i][2];
		color = que[i][3];
		if(arr[x][y] == 'T' && color == 0){
			return dis[x][y][dir][color];
		}
		for(int k=0 ; k<3 ; k++){
			nx = x + co[k] * dx[dir];
			ny = y + co[k] * dy[dir];
			ndir = (dir + dd[k])%4;
			ncolor = (color+co[k])%5;
			if(nx<0 || nx>=n || ny<0 || ny>=m || arr[nx][ny] == '#') continue;
			if(!vis[nx][ny][ndir][ncolor]){
				vis[nx][ny][ndir][ncolor] = true;
				dis[nx][ny][ndir][ncolor] = dis[x][y][dir][color] + 1;
				que[j][0] = nx;
				que[j][1] = ny;
				que[j][2] = ndir;
				que[j][3] = ncolor;
				j++;
			}
		}
	}
	return -1;
}

int main(){
	while(cin>>n>>m && (n!=0 && m!=0)){
		if(Case>1) cout<<"\n";
		for(int i=0 ; i<n ; i++){
			for(int j=0 ; j<m ; j++){
				for(int k=0 ; k<4 ; k++){
					for(int l=0 ; l<5 ; l++){
						vis[i][j][k][l] = false;
						dis[i][j][k][l] = MaxN;
					}
				}
				cin>>arr[i][j];
				if(arr[i][j] == 'S'){
					start_x=i;
					start_y=j;
				}
				else if(arr[i][j] == 'T'){
					end_x = i;
					end_y = j;
				}
			}
		}
		ans = BFS();
		if(ans != -1){
			cout<<"Case #"<<Case++<<"\n"<<"minimum time = "<<ans<<" sec\n";
		}
		else{
			cout<<"Case #"<<Case++<<"\n"<<"destination not reachable\n";
		}
	}

	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(nm)$

每筆測資 BFS 時間複雜度為 狀態數 $\times$ 操作的數量 $= 20nm \times 3$，大約是 $O(nm)$

每筆測資總時間複雜度約為 $O(nm)$