华为机试-竖直四子棋问题C++解法

题目链接在此https://zhuanlan.zhihu.com/p/645259194，这位大佬是用Python实现的

【输入描述】

输入为2行，第一行指定棋盘的宽和高，为空格分隔的两个数字:第二行依次间隔指定红蓝双方的落子步骤，第1步为红方的落子，第2步为蓝方的落子，第3步为红方的落子以此类推。

步骤由空格分隔的一组数字表示，每个数字为落子的列的编号(最左边的列编号为1，往右递增)。用例保证数字均为32位有符号数。

【输出描述】

如果落子过程中红方获胜，输出N,red;

如果落子过程中蓝方获胜，输出N,blue;

如果出现非法的落子步骤，输出N,error。

N为落子步骤的序号，从1开始。如果双方都没有获胜，输出0,draw。非法落子步骤有两种，一是列的编号超过棋盘范围，二是在一个已经落满子的列上落子。N和单词red、blue、draw、error之间是英文逗号连接。

我的代码如下：

//依旧暴力法，但是需要考虑的是checkWin函数没有检查当前位置作为4连中第2个、第3个或第4个棋子的情况，我有点没招了，各位大佬有更好的办法请提点小女子一二好吗

#include <iostream>

#include <string>

#include <vector>

#include <sstream>

using namespace std;

bool checkWin(vector<vector<int>>& board, int row, int col, int player, int height, int width) {

//横、竖、左斜、右斜

if (col + 3 < width) {//向右

if (board[row][col] == player && board[row][col + 1] == player &&

board[row][col + 2] == player && board[row][col + 3] == player) {

return true;

}

}

if (col - 3 >= 0) {//向左

if (board[row][col] == player && board[row][col - 1] == player &&

board[row][col - 2] == player && board[row][col - 3] == player) {

return true;

}

}

if (row + 3 < height) {//向下，没有向上

if (board[row][col] == player && board[row + 1][col] == player &&

board[row + 2][col] == player && board[row + 3][col] == player) {

return true;

}

}

if (row + 3 < height && col + 3 < width) {//右下

if (board[row][col] == player && board[row + 1][col + 1] == player &&

board[row + 2][col + 2] == player && board[row + 3][col + 3] == player) {

return true;

}

}

if (row + 3 < height && col - 3 >= 0) {//左下

if (board[row][col] == player && board[row + 1][col - 1] == player &&

board[row + 2][col - 2] == player && board[row + 3][col - 3] == player) {

return true;

}

}

if (row - 3 >= 0 && col - 3 >= 0) {//左上

if (board[row][col] == player && board[row - 1][col - 1] == player &&

board[row - 2][col - 2] == player && board[row - 3][col - 3] == player) {

return true;

}

}

if (row - 3 >= 0 && col + 3 < width) {//右上

if (board[row][col] == player && board[row - 1][col + 1] == player &&

board[row - 2][col + 2] == player && board[row - 3][col + 3] == player) {

return true;

}

}

//这里偷懒了

//原来的checkWin函数没有检查当前位置作为4连中第2个、第3个或第4个棋子的情况

if (row - 1 >= 0 && col - 1 >= 0 &&

row + 2 < height && col + 2 < width) {

if (board[row - 1][col - 1] == player &&

board[row][col] == player &&

board[row + 1][col + 1] == player &&

board[row + 2][col + 2] == player) {

return true;

}

}

return false;

}

int main() {

//第一行指定棋盘的宽和高，为空格分隔的两个数字

int width, height;

//直接使用cin读取两个数字，会自动跳过空白字符

cin >> width >> height;

//清除第一行后的换行符，否则会被后面的getline读取

cin.ignore();

//第二行依次间隔指定红蓝双方的落子步骤

string s2;

vector<int> nums;

getline(cin, s2);

stringstream ss(s2);

int num;

while (ss >> num) {

nums.push_back(num);

}

//不能超出有效列编号范围

//.size()作用于容器（vector、string、list）

for (int i = 0; i < nums.size(); i++) {

if (nums[i]<1 || nums[i] >width) {

cout << i + 1 << "," << "error";

return 0;

}

}

//题目要求的输出格式：步数、获胜玩家

//构造一个矩阵

vector<vector<int>> board(height, vector<int>(width, 0));

//每列当前棋子数

vector<int> colHeight(width, 0);

//存放走完后的棋盘，空0，红1，蓝2

for (int step = 0; step < nums.size(); step++) {

int moveCol = nums[step] - 1;

int player = (step % 2 == 0) ? 1 : 2;

string playerName = (player == 1) ? "red" : "blue";

if (colHeight[moveCol] >= height) {

cout << step + 1 << ",error";

return 0;

}

//行，放入数组中要-1

int row = height - colHeight[moveCol] - 1;

board[row][moveCol] = player;

colHeight[moveCol]++;

//检查是否获胜,至少要第七步时才能实现四连击

if(step + 1 >= 7) {

if (checkWin(board, row, moveCol, player, height, width)) {

cout << step + 1 << "," << playerName << endl;

return 0;

}

}

}

cout << "0,draw" << endl;

return 0;

}