题目：

输入棋盘：1 1 2 3 2 3
                  3 3 2 3 3 3
                  2 2 2 3 3 3
                  1 2 2 2 3 3
                  2 1 1 2 3 1     (其中1代表空，2代表白子，3代表黑子）
输出：白棋活子个数，黑棋活子个数

来源：华为校招实习生笔试题第二题

                 

#include <iostream>
#include <string>
#include <vector>
#include <array>
using namespace std;class Solution{
public:int breathe; // 气int count; //int result[2]; // 结果，活子个数，0白子，1黑子// 函数四：查看棋盘void watch(vector<vector<int>> &arr){for (int i = 0; i < arr.size(); i++){for (int j = 0; j < arr[i].size(); j++){cout << arr[i][j] << "  ";}cout << endl;}}// 函数三：找到arr里面的值为a的数替换为b，并return a的数目int change(vector<vector<int>> &arr, int a, int b){int changeNum = 0;for (int i = 0; i < arr.size(); i++){for (int j = 0; j < arr[i].size(); j++){if (arr[i][j] == a) {arr[i][j] = b;changeNum++;}}}return changeNum;}// 函数一：遍历所有棋子void solve(vector<vector<int>> &arr){breathe = 0;count = 0;result[0] = 0;  // 活白子结果result[1] = 0;for (int i = 0; i < arr.size(); i++){for (int j = 0; j < arr[i].size(); j++){// 遍历到已经处理过的子和空。矩阵0代表遍历过，1代表为无子if (arr[i][j] == 0 || arr[i][j] == 1) continue;// 遍历到白子，找到所有与之相连的子、气if (arr[i][j] == 2){deepFirst(arr, 2, i, j);watch(arr);breathe = change(arr, -1, 1); // 回溯if (breathe >= 2){result[0] += count;}breathe = 0;    // 回溯count = 0;}// 遍历到黑子，找到所有与之相连的子、气if (arr[i][j] == 3){deepFirst(arr, 3, i, j);watch(arr);breathe = change(arr, -1, 1); // 回溯if (breathe >= 2){result[1] += count;}breathe = 0;    // 回溯count = 0;}}}}// 函数二：①找气   ②找相连的相同子，处理过的子置为0// 子状态，空为1，数过的空为-1，处理过黑白子置为0，黑子3，白子2void deepFirst(vector<vector<int>> &arr, int type, int i, int j){// 该子越界if (i < 0 || i >= arr.size() || j < 0 || j >= arr[0].size())  return;   // 该子为1，空if (arr[i][j] == 1){   arr[i][j] = -1;return;}// 该子不匹配else if (arr[i][j] != type)  {return;}// 该子为相连的子count++;arr[i][j] = 0;// 递归deepFirst(arr, type, i + 1, j);deepFirst(arr, type, i - 1, j);deepFirst(arr, type, i, j+1);deepFirst(arr, type, i, j-1);}
};int main(){int N = 5;vector<vector<int>> arr = {{ 1, 1, 2, 3, 2, 3 },{ 3, 3, 2, 3, 3, 3 },{ 2, 2, 2, 3, 3, 3 },{ 1, 2, 2, 2, 3, 3 },{ 2, 1, 1, 2, 3, 1 }};Solution solution;solution.solve(arr);cout << solution.result[0] << "  " << solution.result[1];while (1);return 0;
}