题目
原文：
Design an algorithm to figure out if someone has won in a game of tic-tac-toe.
译文：
设计算法检查某人是否赢得了井字游戏。
解答
假设这个检查某人是否赢得了井字游戏的函数为HasWon，那么我们第一步要向面试官确认， 这个函数是只调用一次，还是要多次频繁调用。如果是多次调用， 我们可以通过预处理来得到一个非常快速的版本。
方法一：如果HasWon函数需要被频繁调用
对于井字游戏，每个格子可以是空，我的棋子和对方的棋子3种可能，总共有3^9 = 19683 种可能状态。我们可以把每一种状态转换成一个整数， 预处理时把这个状态下是否有人赢得了井字游戏保存起来，每次检索时就只需要O(1)时间。 比如每个格子上的3种状态为0(空)，1(我方棋子)，2(对方棋子)，棋盘从左到右， 从上到下依次记为0到8，那么任何一个状态都可以写成一个3进制的数，再转成10进制即可。 比如，下面的状态：
1
2
3
4
5
1 2 2
2 1 1
2 0 1
可以写成:
122211201=1*3^8 + 2*3^7 +...+ 0*3^1 + 1*3^0
如果只需要返回是否有人赢，而不需要知道是我方还是对方。 那可以用一个二进制位来表示是否有人赢。比如上面的状态，1赢， 就可以把那个状态转换成的数对应的位置1。如果需要知道是谁赢， 可以用一个char数组来保存预处理结果。
方法二：如果HasWon函数只被调用一次或很少次
如果HasWon函数只被调用一次或很少次，那我们就没必要去预存结果了， 直接判断一下就好。只为一次调用去做预处理是不值得的。
代码如下，判断n*n的棋盘是否有人赢，即同一棋子连成一线：
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
#include <iostream>
using namespace std;
enum Check{
ROW, COLUMN, DIAGONAL, REDIAGONAL
};
int CheckRowColumn(int board[], int n, Check check){
int type = 0;
for(int i=0; i<n; ++i){
bool found = true;
for(int j=0; j<n; ++j){
int k = 0;
if(check == ROW)
k = i * n + j;
else
k = i + j * n;
if(j == 0){
type = board[k];
}
else if(board[k] != type){
found = false;
break; // 有一个不满足，检查下一行
}
}
if(found) return type;
}
return 0;
}
int CheckDiagonal(int board[], int n, Check check){
int type = 0;
bool found = true;
// 主对角
for(int i=0; i<n; ++i){
int k = 0;
if(check == DIAGONAL)
k = i + i * n;
else
k = i + (n-1-i) * n;
if(i == 0){
type = board[k];
}
else if(board[k] != type){
found = false;
break;
}
}
if(found) return type;
return 0;
}
int HasWon(int board[], int n){
int type = 0;
type = CheckRowColumn(board, n, ROW);
if(type != 0) return type;
type = CheckRowColumn(board, n, COLUMN);
if(type != 0) return type;
type = CheckDiagonal(board, n, DIAGONAL);
if(type != 0) return type;
type = CheckDiagonal(board, n, REDIAGONAL);
if(type != 0) return type;
return 0;
}
int main(){
int n = 3; // 3*3
int board[] = {
2, 2, 1,
2, 1, 1,
1, 2, 0,
};
int type = HasWon(board, n);
if(type != 0)
cout<<type<<" won!"<<endl;
else
cout<<"nobody won!"<<endl;
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/02/20/19.2/
