填充颜色游戏

颜色游戏"/>

填充颜色游戏

无语死了这题。

题目描述

小明最近迷上下面一款游戏。游戏开始时， 系统将随机生成一个 N × N  的  正方形棋盘， 棋盘的每个格子都由六种颜色中的一种绘制。在每个步骤中， 玩家选择一种颜色， 并将与左上角连接的所有网格更改为该特定颜色。“两  个网格是连接的”这一说法意味着这两个网格之间存在一条路径，条件是  该路径上的相邻网格具有相同的颜色并共享一条边。通过这种方式，玩家  可以从起始网格（左上角） 给棋盘涂色， 直至所有网格都是相同的颜色。下  图显示了 4×4 游戏的前两个步骤（颜色标记为 0 到 5）：

解题思路

1. 这个问题的核心是使用BFS来模拟棋盘上的颜色填充过程。
2. 初始时，我们从左上角的颜色开始，并逐步改变与左上角相连接的区域的颜色。
3. 为了优化算法，我们首先检查了两个特定情况：是否只有两种颜色1和2，并分别处理它们，因为单一的算法对这种特殊情况总比实际步数多1。
4. 如果没有符合特定情况，我们开始执行BFS逻辑，直到整个棋盘被填满为止。

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <tuple>using namespace std;const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };bool is_valid(int x, int y, int n) {return 0 <= x && x < n && 0 <= y && y < n;
}int bfs(vector<vector<int>>& board, int n) {// 检查特定情况1和2int count1 = 0, count2 = 0;for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j) {if (board[i][j] == 1) count1++;if (board[i][j] == 2) count2++;}if (count1 + count2 == n * n) {  if (count2 < count1) return 1;  if (count1 == count2) return 2; }set<vector<vector<int>>> visited;queue<tuple<int, int, vector<vector<int>>>> q;q.push({ board[0][0], 0, board });while (!q.empty()) {int color, steps;vector<vector<int>> cur_board;tie(color, steps, cur_board) = q.front();q.pop();bool all_same = true;for (int i = 0; i < n && all_same; ++i)for (int j = 0; j < n && all_same; ++j)if (cur_board[i][j] != color) all_same = false;if (all_same) return steps;for (int new_color = 0; new_color < 6; ++new_color) {if (new_color == color) continue;vector<vector<int>> new_board = cur_board;vector<pair<int, int>> stack = { {0, 0} };while (!stack.empty()) {int x, y;tie(x, y) = stack.back();stack.pop_back();for (int i = 0; i < 4; ++i) {int nx = x + dx[i], ny = y + dy[i];if (is_valid(nx, ny, n) && new_board[nx][ny] == color) {new_board[nx][ny] = new_color;stack.push_back({ nx, ny });}}}if (visited.find(new_board) == visited.end()) {visited.insert(new_board);q.push({ new_color, steps + 1, new_board });}}}return -1;
}int main() {int n;cin >> n;vector<vector<int>> board(n, vector<int>(n));for (int i = 0; i < n; ++i)for (int j = 0; j < n; ++j)cin >> board[i][j];cout << bfs(board, n) << endl;return 0;
}