17.2 Design an algorithm to figure out if someone has won a game oftic-tac-toe.
这道题让我们判断玩家是否能赢井字棋游戏，有下面几点需要考虑：
1. 判断是否能赢hasWon函数是调用一次还是多次，如果是多次，我们可能为了优化而需要加入一些预处理。
2. 井字棋游戏通常是3x3的大小，我们是否想要实现NxN的大小？
3. 我们需要在代码紧凑，执行速度和代码清晰之间做出选择。
#include <iostream>
#include <string>
#include <vector>
#include <ctime> using namespace std; int convertBoardToInt(vector<string> board) {
int factor = , sum = ;
for (int i = ; i < board.size(); ++i) {
for (int j = ; j < board[i].size(); ++j) {
int v = ;
if (board[i][j] == 'x') v = ;
else if (board[i][j] == 'o') v = ;
sum += v * factor;
factor *= ;
}
}
return sum;
} enum class Piece {Empty, Red, Blue}; enum class Check {Row, Column, Diagonal, ReverseDiagonal}; Piece getIthColor(vector<vector<Piece>> board, int idx, int var, Check check) {
int N = board.size();
if (check == Check::Row) {
return board[idx][var];
} else if (check == Check::Column) {
return board[var][idx];
} else if (check == Check::Diagonal) {
return board[var][var];
} else if (check == Check::ReverseDiagonal) {
return board[N - - var][var];
}
return Piece::Empty;
} Piece getWinner(vector<vector<Piece>> board, int fixed_idx, Check check) {
Piece color = getIthColor(board, fixed_idx, , check);
if (color == Piece::Empty) {
return Piece::Empty;
}
for (int var = ; var < board.size(); ++var) {
if (color != getIthColor(board, fixed_idx, var, check)) {
return Piece::Empty;
}
}
return color;
} // work for 3*3 board
Piece hasWon1(vector<vector<Piece>> board) {
for (int i = ; i < board.size(); ++i) {
if (board[i][] != Piece::Empty && board[i][] == board[i][] && board[i][] == board[i][]) {
return board[i][];
}
if (board[][i] != Piece::Empty && board[][i] == board[][i] && board[][i] == board[][i]) {
return board[][i];
}
}
if (board[][] != Piece::Empty && board[][] == board[][] && board[][] == board[][]) {
return board[][];
}
if (board[][] != Piece::Empty && board[][] == board[][] && board[][] == board[][]) {
return board[][];
}
return Piece::Empty;
} // N*N board
Piece hasWon2(vector<vector<Piece>> board) {
int N = board.size();
Piece winner = Piece::Empty;
for (int i = ; i < N; ++i) {
winner = getWinner(board, i, Check::Row);
if (winner != Piece::Empty) return winner;
winner = getWinner(board, i, Check::Column);
if (winner != Piece::Empty) return winner;
}
winner = getWinner(board, -, Check::Diagonal);
if (winner != Piece::Empty) return winner;
winner = getWinner(board, -, Check::ReverseDiagonal);
if (winner != Piece::Empty) return winner;
return Piece::Empty;
} // N*N board
Piece hasWon3(vector<vector<Piece>> board) {
int N = board.size(), row = , col = ;
for (row = ; row < N; ++row) {
if (board[row][] != Piece::Empty) {
for (col = ; col < N; ++col) {
if (board[row][col] != board[row][col - ]) {
break;
}
}
if (col == N) return board[row][];
}
}
for (col = ; col < N; ++col) {
if (board[][col] != Piece::Empty) {
for (row = ; row < N; ++row) {
if (board[row][col] != board[row - ][col]) {
break;
}
}
if (row == N) return board[][col];
}
}
if (board[][] != Piece::Empty) {
for (row = ; row < N; ++row) {
if (board[row][row] != board[row - ][row - ]) {
break;
}
}
if (row == N) return board[][];
}
if (board[N - ][] != Piece::Empty) {
for (row = ; row < N; ++row) {
if (board[N - row - ][row] != board[N - row][row - ]) {
break;
}
}
if (row == N) return board[N - ][];
}
return Piece::Empty;
} // N*N board
Piece hasWon4(vector<vector<Piece>> board) {
int N = board.size(), i = , j = ;
vector<Piece> pieces{Piece::Red, Piece::Blue};
for (Piece color : pieces) {
for (i = ; i < N; ++i) {
bool maybe_col = true, maybe_row = true;
for (j = ; j < N; ++j) {
if (board[i][j] != color) maybe_row = false;
if (board[j][i] != color) maybe_col = false;
}
if (maybe_col || maybe_row) return color;
}
bool maybe_diag = true, maybe_revdiag = true;
for (i = ; i < N; ++i) {
if (board[i][i] != color) maybe_diag = false;
if (board[N - i - ][i] != color) maybe_revdiag = false;
}
if (maybe_diag || maybe_revdiag) return color;
}
return Piece::Empty;
} Piece convertIntToPiece(int i) {
if (i == ) {
return Piece::Blue;
} else if (i == ) {
return Piece::Red;
} else {
return Piece::Empty;
}
} void printVec(vector<vector<int>> v) {
for (int i = ; i < v.size(); ++i) {
for (int j = ; j < v[i].size(); ++j) {
cout << v[i][j] << " ";
}
cout << endl;
}
cout << endl;
} void printPiece(Piece p) {
if (p == Piece::Empty) cout << "Empty" << endl;
else if (p == Piece::Red) cout << "Red" << endl;
else if (p == Piece::Blue) cout << "Blue" << endl;
} int main() {
srand(time(NULL));
for (int k = ; k < ; ++k) {
int N = ;
vector<vector<int>> v(N, vector<int>(N, ));
vector<vector<Piece>> board(N, vector<Piece>(N));
for (int i = ; i < N; ++i) {
for (int j = ; j < N; ++j) {
v[i][j] = rand() % ;
board[i][j] = convertIntToPiece(v[i][j]);
}
}
Piece p1 = hasWon1(board);
Piece p2 = hasWon2(board);
Piece p3 = hasWon3(board);
Piece p4 = hasWon4(board);
if (p1 != p2 || p2 != p3 || p3 != p4) {
printPiece(p1);
printPiece(p2);
printPiece(p3);
printPiece(p4);
printVec(v);
}
cout << endl;
}
}