C++刷leetcode（面试题 16.04. 井字游戏）【数据结构】
题目描述：设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。
以下是井字游戏的规则：
玩家轮流将字符放入空位（" "）中。
第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"。
"X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。
当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。
当所有位置非空时，也算为游戏结束。
如果游戏结束，玩家不允许再放置字符。
如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（"X"或"O"）；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。
示例 1：
输入： board = ["O X"," XO","X O"]
输出： "X"
示例 2：
输入： board = ["OOX","XXO","OXO"]
输出： "Draw"
解释： 没有玩家获胜且不存在空位
示例 3：
输入： board = ["OOX","XXO","OX "]
输出： "Pending"
解释： 没有玩家获胜且仍存在空位
提示：
1 <= board.length == board.length <= 100
输入一定遵循井字棋规则
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/tic-tac-toe-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
string tictactoe(vector<string>& board) {
int len = board.size();
string res = "Draw";
//行
bool flag = false;
for(int i = 0; i < len; i++){
stack<char> temp1;
for(int j = 0 ;j < len; j++){
if(board == ' ') flag = true;
if(temp1.empty() ){
temp1.push(board);
}else if(temp1.top() == board){
temp1.push(board);
if(temp1.size() == len && board != ' '){
res = board;
return res;
}
}
}
}
//列
for(int i = 0; i < len; i++){
stack<char> temp2;
for(int j = 0 ;j < len; j++){
if(board == ' ') flag = true;
if(temp2.empty()){
temp2.push(board);
}else if(temp2.top() == board){
temp2.push(board);
if(temp2.size() == len &&board != ' '){
res = board;
return res;
}
}
}
}
//斜对角
inti = 0;
stack<int> temp3;
for(int j = 0 ; j < len; j++){
if(temp3.empty() || temp3.top() == board){
temp3.push(board);
}else if(temp3.top() != board){
break;
}
i++;
}
if(temp3.size() == len&& temp3.top() != ' ') res = temp3.top();
i = len - 1;
stack<int> temp4;
for(int j = 0; j < len; j++){
if(temp4.empty() || temp4.top() == board){
temp4.push(board);
}else if(temp4.top() != board){
break;
}
i--;
}
if(temp4.size() == len && temp4.top() != ' ') res = temp4.top();
if(res == "O" || res == "X") return res;
else if(res == "Draw" && flag == true) return "Pending";
return res;
}
}; 考察对基本框架的熟练程度
页:
[1]