XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 4-3UVa220 - Othello

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 3.1k 阅读时长 ≈ 3 分钟

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO 代码：（Accepted，0 ms）

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
//UVa 220 - Othello
#include<iostream>
char Board[11][11], Current, Command[5];
bool Flag, L_Refresh;//flag用于空格的输出,同时可以判断出本局是不是当前颜色的棋子无路可走
int Times, Num[2];//Num:0白1黑
int Rx[] = { 0, 0,1,-1,1,-1,1,-1 };
int Ry[] = { 1,-1,0, 0,1,-1,-1,1 };
inline char oppo() { return (Current == 'W' ? 'B' : 'W'); }

bool judge(int i, int j, int x, int y, bool is_print) {
	int ii = i + 1, jj = j + 1, flg = 0;
	while ((i += x) < 8 && (j += y) < 8 && i >= 0 && j>=0) {
		if (Board[i][j] == '-') break;
		if (Board[i][j] == Current) {
			if (!flg) break;
			if (is_print) {
				if (Flag) printf(" ");
				printf("(%d,%d)", ii, jj);
			}
			if (!Flag) Flag = true;
			return true;
		}
		++flg;
	}
	return false;
}

void change(int i, int j, int x, int y) {
	int n = 0;
	while (Board[i += x][j += y] != Current) {
		Board[i][j] = Current, ++n;
	}
	Current == 'W' ? (Num[0] += n, Num[1] -= n) : (Num[0] -= n, Num[1] += n);
}

void L(bool is_print) {
	L_Refresh = 1, Flag = 0;
	for (int i = 0;i < 8;++i)  for (int j = 0;j < 8;++j) {
		if (Board[i][j] != '-') continue;
		for (int l = 0;l < 8;++l)
			if (judge(i, j, Rx[l], Ry[l], is_print))  break;
	}
	if (is_print) Flag ? printf("\n") : printf("No legal move.\n");
}

void M() {
	char i = Command[1] - 49, j = Command[2] - 49;
	if (!L_Refresh) L(0);
	if (!Flag) Current = oppo();
	for (int l = 0;l < 8;++l)
		if (judge(i, j, Rx[l], Ry[l], 0)) change(i, j, Rx[l], Ry[l]);
	Current == 'W' ? Num[0] += 1 : Num[1] += 1;
	Board[i][j] = Current;
	Current = oppo();
	L_Refresh = 0;
	printf("Black - %2d White - %2d\n", Num[1], Num[0]);
}

void Q() {
	for (int i = 0;i < 8;++i) printf("%s\n", Board[i]);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	scanf("%d", &Times);
	while (Times--) {
		for (int i = 0;i < 8;++i) scanf("%s", Board[i]);
		scanf("\n%c", &Current);
		L_Refresh = 0;
		Num[0] = Num[1] = 0;
		for (int i = 0;i < 8;++i)  for (int j = 0;j < 8;++j) {
			if (Board[i][j] == 'W') ++Num[0];
			else if (Board[i][j] == 'B') ++Num[1];
		}
		while (scanf("%s", Command) && Command[0] != 'Q')
			Command[0] == 'L' ? L(1) : M();
		Q();
		if (Times) printf("\n");
	}
	return 0;
}

分析： 在uDebug上调试都对了，提交时还是无限WA，挠的头发都要掉光了，最后发现忘记把freopen("in.txt", "r", stdin);加注释了@。@。。。。气得我笑出声。 首先是List all possible moves for the current player.有上下左右与4条斜线8种情况。8*8个格子每个都要检索一遍。先judge()查看每个位置各个方向是否legal，如果可以放置，输出之。输出直接放在judge里了，不高兴写入字符数组了，后面M()也会用到judge，这时不希望他输出，于是给judge()加了个is_print变量来控制。尽量代码重用。还有对于这八个方向，我一开始是用的傻傻的枚举， 

1
2
3
4
5
6
7
8
if (judge(i, j, 0, 1, is_print)) continue;
if (judge(i, j, 0, -1, is_print)) continue;
if (judge(i, j, 1, 0, is_print)) continue;
if (judge(i, j, -1, 0, is_print)) continue;
if (judge(i, j, 1, 1, is_print)) continue;
if (judge(i, j, -1, -1, is_print)) continue;
if (judge(i, j, 1, -1, is_print)) continue;
if (judge(i, j, -1, 1, is_print)) continue;
后来VJ上看到别人用以下数组， 
1
int rx[] = { 0, 0,1,-1,1,-1,1,-1 }， ry[] = { 1,-1,0, 0,1,-1,-1,1 };
一开始没看懂他这奇怪的数组干嘛的，看懂后真的是令我拍大腿叫绝。 所以现在只需一个循环 
1
2
for (int l = 0;l < 8;++l)
		if (judge(i, j, Rx[l], Ry[l], 0)) change(i, j, Rx[l], Ry[l]);
即可，真心方便。下面M()函数也一样。 还有就是L_Refresh的作用。系统有可能一口气执行多次L()（当然我不确定，只是有可能），也可能未执行就执行M，这时需要知道是不是无合法操作，还得先执行L()，L_Refresh就是用来检测L()有没有执行过，且防止其重复执行多次。 还有那个输出，比如“Black - 1 White - 4”，数字1和4在输出时应用“ %2d”输出，而不是两个空格键。之前看题目“Black - xx White - yy”的xx、yy没看懂，后来才知道是占两个格子的意思。