Koios1143的筆記

UVa 258

發表於 分類於

UVa 258

題目

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

給一個 $n \times m$ 的方格，在最外圍保證只有兩個點是 .，表示起點以及終點，其餘都是 *

起點會有一束光源源不絕射入，如果遇到地圖當中的鏡子 / 或是 \ 就會被反射，這裡的鏡子都會是以 $45^{\circ}$ 放置，也就是說光會轉向 $90^{\circ}$

每個鏡子都可以選擇要是 / 或是 \，輸出其中一組可以使光照射出終點的盤面

想法

首先先找到起點以及終點，因為是光所以其實起點終點相反也沒關係

再來對於光來說方向也是重要的狀態，所以也同時先找到起點光射入的方向

找到之後嘗試跟著方向走，如果遇到鏡子就分成兩種情況

  1. 跟著鏡子反射，然後固定這個鏡子的方向
  2. 如果之前沒有光線經過這個鏡子，那我們就嘗試轉方向

這裡很重要的是要記錄這個鏡子有沒有被光線走過，如果有光線經過而我們又調整鏡子的方向，可能會導致光線不會走到現在的點上

那麼一直走到出口就找到答案了

因為每次都是一路走到底，所以可以用 DFS 去嘗試每種走法

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
//By Koios1143
#include<iostream>
using namespace std;
// 0: up , 1: right, 2: down, 3: left
int n ,m, start_x, start_y, end_x, end_y, start_dir, end_dir, nx, ny, n_dir;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char arr[55][55];
bool used[55][55], out=false, found;

void DFS(int x, int y, int dir){
	if(found) return;
	if(x==end_x && y==end_y){
		found=true;
		for(int i=0 ; i<n ; i++){
			for(int j=0 ; j<m ; j++){
				cout<<arr[i][j];
			}
			cout<<"\n";
		}
		return;
	}
	if(arr[x][y] == '.'){
		nx = x + dx[dir];
		ny = y + dy[dir];
		DFS(nx, ny, dir);
	}
	else if(arr[x][y] == '*'){
		return;
	}
	else{
		if(arr[x][y] == '/'){
			bool tmp=used[x][y];
			used[x][y] = true;
			n_dir = dir^1;
			nx = x + dx[n_dir];
			ny = y + dy[n_dir];
			DFS(nx, ny, n_dir);
			used[x][y] = tmp;
			// spin mirror
			if(!used[x][y]){
				used[x][y] = true;
				arr[x][y] = '\\';
				n_dir = 3-dir;
				nx = x + dx[n_dir];
				ny = y + dy[n_dir];
				DFS(nx, ny, n_dir);
				arr[x][y] = '/';
				used[x][y] = false;
			}
		}
		else{
			bool tmp=used[x][y];
			used[x][y] = true;
			n_dir = 3-dir;
			nx = x + dx[n_dir];
			ny = y + dy[n_dir];
			DFS(nx, ny, n_dir);
			used[x][y] = tmp;
			// spin mirror
			if(!used[x][y]){
				used[x][y] = true;
				arr[x][y] = '/';
				n_dir = dir^1;
				nx = x + dx[n_dir];
				ny = y + dy[n_dir];
				DFS(nx, ny, n_dir);
				arr[x][y] = '\\';
				used[x][y] = false;
			}
		}
	}
}

int main(){
	while(cin>>m>>n && (m!=-1 && n!=-1)){
		if(out) cout<<"\n";
		else out=true;
		
		found=false;		
		start_x = start_y = end_x = end_y = -1;
		for(int i=0 ; i<n ; i++){
			for(int j=0 ; j<m ; j++){
				used[i][j] = false;
				cin>>arr[i][j];
				if((i==0 || i==n-1 || j==0 || j==m-1) && arr[i][j]=='.'){
					if(start_x == -1){
						start_x = i;
						start_y = j;
						if(i==0) start_dir = 2;
						else if(i==n-1) start_dir = 0;
						else if(j==0) start_dir = 1;
						else start_dir = 3;
					}
					else{
						end_x = i;
						end_y = j;
					}
				}
			}
		}
		DFS(start_x, start_y, start_dir);
	}
	
	return 0;
}

時間複雜度分析

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

DFS 每層最多有 $2$ 種選擇，最多有 $nm$ 層

DFS 時間複雜度為 $O(2^{nm})$

每筆測資總時間複雜度為 $O(nm + 2^{nm})$