国际象棋AI：车和后控制的格子计数 - C++实现 - 常规

{"title":"国际象棋AI：车和后控制的格子计数 - C++实现","description":"本文介绍了如何使用C++开发一个国际象棋AI，该AI能够计算棋盘上车和后所控制的格子数量。提供了详细的算法思路、代码实现以及时间复杂度分析。","keywords":"国际象棋, AI, 人工智能, 机器学习, 车, 后, 控制, 格子, 计数, C++, 代码, 实现, 时间复杂度","content":"题目描述：人胖了就容易打瞌睡，打瞌睡又会导致长胖，这对小X的减重计划很不利，于是小X决定做点动脑子的事来抵御瞌睡虫的进袭，小X决定响应国务\n 院的号召投身到人工智能的研究开发大潮中去，具体研究什么好呢？小X再三思考后决定开发国际象棋的人工智能软件，虽然国际象棋的软件已经能\n 够战胜人类世界冠军了，但那是基于搜索的AI（AI是人工智能的简称），小X想写一个基于机器学习的国际象棋AI,目标是战胜旧M的深蓝，小X的国\n 际象棋水平也不差，曾获得过市青少年比赛的冠军，机器学习顾名思义就是让机器像人一样学习，小X首先训练机器学习棋子对棋盘的控制，具体做\n 法是小X先在棋盘上放置若干个车和后，然后让机器判断有多少个格子没有被车和后控制到。\n 车和后的吃子规则如下：车：横、竖均可以走，步数不受限制，但不能斜着走。后：横、竖、斜都可以走，步数不受限制。无论是车还是后都不能\n 越过棋子去吃子，用作训练的国际象棋棋盘可以放大缩小，并不限于8x8的棋盘，车和后所在的位置当然是被控制的，它们能走到的位置也都被控\n 制。\n 输入：第一行包含一个正整数n,表示棋盘的大小。\n 接下来n行，每行n个整数，其中0表示棋盘上这个格子为空的，1表示为车，2表示为后。\n 输出：一行一个整数，表示没有被控制到的格子数量。\n样例组:\n样例输入:\n5\n0 0 0 0 0\n0 1 0 1 0\n0 0 2 0 0\n0 1 0 1 0\n0 0 0 0 0\n样例输出:\n4\n用C++，尽量降低时间复杂度，确保答案正确内容：思路：\n首先遍历整个棋盘，找到车和后的位置。\n然后分别以车和后的位置为起点，向四个方向进行搜索，直到遇到边界或者其他棋子。\n在搜索的过程中，将经过的格子标记为已控制。\n最后统计没有被控制到的格子数量即可。\n\n具体实现：\n1. 读取输入的棋盘大小n，并创建一个大小为n的二维数组board表示棋盘。\n2. 使用两个vector<pair<int,int>>分别存储车和后的位置。\n3. 遍历整个棋盘，将车和后的位置保存到对应的vector中。\n4. 创建一个大小为n的二维数组visited表示每个格子是否被控制。\n5. 分别以车和后的位置为起点，向四个方向进行搜索，并将经过的格子标记为已控制。\n6. 统计没有被控制到的格子数量。\n7. 输出结果。\n\n时间复杂度分析：\n遍历整个棋盘的时间复杂度为O(n^2)，搜索的时间复杂度为O(n)，因此总的时间复杂度为O(n^3)。\n\n代码实现如下：\n\n```cpp\n#include \n#include \nusing namespace std;\n\nint main() {\n int n;\n cin >> n;\n vector<vector> board(n, vector(n));\n vector<pair<int, int>> rookPos, queenPos;\n vector<vector> visited(n, vector(n, 0));\n \n // 读取棋盘\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n cin >> board[i][j];\n if (board[i][j] == 1) {\n rookPos.push_back(make_pair(i, j));\n visited[i][j] = 1;\n } else if (board[i][j] == 2) {\n queenPos.push_back(make_pair(i, j));\n visited[i][j] = 1;\n } } } // 搜索 for (auto pos : rookPos) { int x = pos.first; int y = pos.second; // 向上搜索 for (int i = x - 1; i >= 0; i--) { if (board[i][y] != 0) break; visited[i][y] = 1; } // 向下搜索 for (int i = x + 1; i < n; i++) { if (board[i][y] != 0) break; visited[i][y] = 1; } // 向左搜索 for (int j = y - 1; j >= 0; j--) { if (board[x][j] != 0) break; visited[x][j] = 1; } // 向右搜索 for (int j = y + 1; j < n; j++) { if (board[x][j] != 0) break; visited[x][j] = 1; } } for (auto pos : queenPos) { int x = pos.first; int y = pos.second; // 向上搜索 for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] != 0) break; visited[i][j] = 1; } for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] != 0) break; visited[i][j] = 1; } for (int i = x - 1; i >= 0; i--) { if (board[i][y] != 0) break; visited[i][y] = 1; } // 向下搜索 for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) { if (board[i][j] != 0) break; visited[i][j] = 1; } for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) { if (board[i][j] != 0) break; visited[i][j] = 1; } for (int i = x + 1; i < n; i++) { if (board[i][y] != 0) break; visited[i][y] = 1; } // 向左搜索 for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] != 0) break; visited[i][j] = 1; } for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) { if (board[i][j] != 0) break; visited[i][j] = 1; } for (int j = y - 1; j >= 0; j--) { if (board[x][j] != 0) break; visited[x][j] = 1; } // 向右搜索 for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] != 0) break; visited[i][j] = 1; } for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) { if (board[i][j] != 0) break; visited[i][j] = 1; } for (int j = y + 1; j < n; j++) { if (board[x][j] != 0) break; visited[x][j] = 1; } } // 统计没有被控制到的格子数量 int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (visited[i][j] == 0) count++; } } cout << count << endl; return 0;}\n\n希望能帮到你！