Koios1143的筆記

UVa 10196

發表於 分類於

UVa 10196

題目

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

給一個西洋棋盤的盤面，以小寫表示黑色，大寫表示白色

棋盤包含幾種棋子

  • Pawn（士兵，以p或P表示）
  • Knight（騎士，以n或N表示)
  • Bishop（主教，以b或B表示）
  • Rook（城堡，以r或R表示）
  • Queen（皇后，以q或Q表示）
  • King（國王，以k或K表示）

現在給你一個盤面，求是否有 白色/黑色 的國王正處於可以被攻擊的狀態，或是沒有這兩種狀態

保證沒有兩者同時處在可被攻擊狀態的情況

想法

很有趣的實作題w

我們可以直接針對所有在盤面上的棋子都動動看，如果遇到可以攻擊敵方國王就直接輸出

在書寫過程中也許會發現到時常出現重複的問題

這時候就可以好好善用 function 的優勢，讓程式碼變得更加簡潔

並且建議在寫這樣的實作題可以直接在 main 完成，並假定某個 function 能具有什麼功能，等到 main 寫完，再去完成那些 function

這樣寫起來會順暢許多

程式碼

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<iostream>
using namespace std;
int game=1;
int pb[2][2]={{1,-1},{1,1}},pw[2][2]={{-1,-1},{-1,1}};
int knight[8][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
char board[10][10];
bool cango(int x,int y){
    // 判斷是否超出棋盤
	if(x<0 || x>=8 || y<0 || y>=8) return false;
	return true;
}
bool rock(int x, int y, int color){
    // 判斷城堡是否能 check
	char king;
	if(color==0)
		king='K';
	else
		king='k';
	for(int i=x-1 ; i>=0 ; i--){
		//up
		if(board[i][y]==king)
			return true;
		else if(board[i][y]!='.')
			break;
	}
	for(int i=x+1 ; i<8 ; i++){
		//down
		if(board[i][y]==king)
			return true;
		else if(board[i][y]!='.')
			break;
	}
	for(int i=y-1 ; i>=0 ; i--){
		//left
		if(board[x][i]==king)
			return true;
		else if(board[x][i]!='.')
			break;
	}
	for(int i=y+1 ; i<8 ; i++){
		//right
		if(board[x][i]==king)
			return true;
		else if(board[x][i]!='.')
			break;
	}
	return false;
}
bool bishop(int x,int y,int color){
    // 判斷主教是否能 check
	char king;
	if(color==0)
		king='K';
	else
		king='k';
	for(int i=x-1, j=y+1 ; i>=0 && j<8 ; i--, j++){
		// upper right
		if(board[i][j]==king)
			return true;
		else if(board[i][j]!='.')
			break;
	}
	for(int i=x-1, j=y-1 ; i>=0 && j>=0 ; i--, j--){
		// upper left
		if(board[i][j]==king)
			return true;
		else if(board[i][j]!='.')
			break;
	}
	for(int i=x+1, j=y+1 ; i<8 && j<8 ; i++, j++){
		// lower right
		if(board[i][j]==king)
			return true;
		else if(board[i][j]!='.')
			break;
	}
	for(int i=x+1, j=y-1 ; i<8 && j>=0 ; i++, j--){
		// upper left
		if(board[i][j]==king)
			return true;
		else if(board[i][j]!='.')
			break;
	}
	return false;
}
bool check_over(char chess, int x, int y, int color){
    // 確認是否能 check
	char ch=tolower(chess);
	if(ch=='p'){
		// pawn
		if(color==0){
			// black
			for(int i=0 ; i<2 ; i++){
				int nx=x+pb[i][0];
				int ny=y+pb[i][1];
				if(cango(nx,ny) && board[nx][ny]=='K')
					return true;
			}
		}
		else{
			//white
			for(int i=0 ; i<2 ; i++){
				int nx=x+pw[i][0];
				int ny=y+pw[i][1];
				if(cango(nx,ny) && board[nx][ny]=='k')
					return true;
			}
		}
	}
	else if(ch=='r'){
		// rook
		return rock(x,y,color);
	}
	else if(ch=='b'){
		// bishop
		return bishop(x,y,color);
	}
	else if(ch=='q'){
		// queen
		return rock(x,y,color) || bishop(x,y,color);
	}
	else if(ch=='n'){
		// knight
		char king;
		if(color==0)
			king='K';
		else
			king='k';
		for(int i=0 ; i<8 ; i++){
			int nx=x+knight[i][0];
			int ny=y+knight[i][1];
			if(cango(nx,ny) && board[nx][ny]==king)
				return true;
		}
		return false;
	}
	return false;
}
int main(){
	while(true){
		bool end=false;
		for(int i=0 ; i<8 ; i++){
			for(int j=0 ; j<8 ; j++){
				cin>>board[i][j];
				if(board[i][j]!='.')
					end=true;
			}
		}
		if(!end)
			break;
		bool found=false;
		for(int i=0 ; i<8 && !found ; i++){
			for(int j=0 ; j<8 && !found ; j++){
				if(board[i][j]=='.' || board[i][j]=='k' || board[i][j]=='K')
					continue;
				if(islower(board[i][j])){
					// black
					if(check_over(board[i][j], i, j, 0)){
						cout<<"Game #"<<game<<": white king is in check.\n";
						game++;
						found=true;
					}
				}
				else{
					// white
					if(check_over(board[i][j], i, j, 1)){
						cout<<"Game #"<<game<<": black king is in check.\n";
						game++;
						found=true;
					}
				}
			}
		}
		if(!found){
			cout<<"Game #"<<game<<": no king is in check.\n";
			game++;
		}
	}
	return 0;
}

時間複雜度分析

假設棋盤邊長為 $N$

輸入時間複雜度為 $O(N^2)$

所有棋子針對任意方向的搜尋時間複雜度都視為 $O(1)$

最差情況盤面上每個點都需要搜尋過，時間複雜度為 $O(N^2)$

每筆測資時間複雜度為 $O(2 \times N^2)$ 約為 $O(N^2)$