题意分析

1、游戏目标：选择一个目标字符（如 $'A'$），通过最少次数的相邻交换，使得至少一个$2×22×2$ 的子方格中所有字符都变为目标字符。 2、交换规则：每次只能交换水平或垂直相邻的两个字符。 3、策略计数：不同目标字符的选择即使交换顺序相同也算作不同策略。

解题思路

1、 枚举目标字符：对于每个测试用例，分别尝试将 'A'、'B'、'C' 和 'D' 作为目标字符。 2、 BFS 搜索最小交换次数：对于每个目标字符，使用广度优先搜索（BFS）计算从初始状态到任意一个 $2 \times 2$ 子方格全为目标字符的最小交换次数。 3、 统计最优策略：记录所有目标字符的最小交换次数，并统计达到最小次数的策略总数。

C++实现

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

const int N = 4;
const int INF = INT_MAX;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

string gridToString(const vector<vector<char>>& grid) {
    string s;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            s += grid[i][j];
        }
    }
    return s;
}

vector<vector<char>> stringToGrid(const string& s) {
    vector<vector<char>> grid(N, vector<char>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            grid[i][j] = s[i * N + j];
        }
    }
    return grid;
}

bool isWinning(const vector<vector<char>>& grid, char target) {
    for (int i = 0; i < N - 1; ++i) {
        for (int j = 0; j < N - 1; ++j) {
            if (grid[i][j] == target && grid[i][j + 1] == target &&
                grid[i + 1][j] == target && grid[i + 1][j + 1] == target) {
                return true;
            }
        }
    }
    return false;
}

// 启发式函数：计算当前状态到任意目标状态的最小可能步数（这里只是示例，可能不准确）
int heuristic(const string& state, char target) {
    // 简单示例：返回0（不使用有效启发式）或尝试实现一个更复杂的启发式
    return 0; // 需要实现更复杂的启发式来有效剪枝
}

struct State {
    string grid;
    int swaps;
    int g; // 已用步数
    int h; // 启发式估计步数
    int f() const { return g + h; }
    bool operator>(const State& other) const { return f() > other.f(); }
};

pair<int, int> aStar(const vector<vector<char>>& startGrid, char target) {
    priority_queue<State, vector<State>, greater<State>> pq;
    unordered_set<string> visited;
    string startState = gridToString(startGrid);
    pq.push({startState, 0, 0, heuristic(startState, target)});
    visited.insert(startState);

    int minSwaps = INF;
    int strategyCount = 0;

    while (!pq.empty()) {
        auto [currentState, swaps, g, h] = pq.top();
        pq.pop();

        vector<vector<char>> currentGrid = stringToGrid(currentState);

        if (isWinning(currentGrid, target)) {
            if (swaps < minSwaps) {
                minSwaps = swaps;
                strategyCount = 1;
            } else if (swaps == minSwaps) {
                strategyCount++;
            }
            continue;
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                for (int d = 0; d < 4; ++d) {
                    int ni = i + dx[d];
                    int nj = j + dy[d];
                    if (ni >= 0 && ni < N && nj >= 0 && nj < N) {
                        swap(currentGrid[i][j], currentGrid[ni][nj]);
                        string newState = gridToString(currentGrid);
                        if (visited.find(newState) == visited.end()) {
                            visited.insert(newState);
                            pq.push({newState, swaps + 1, g + 1, heuristic(newState, target)});
                        }
                        swap(currentGrid[i][j], currentGrid[ni][nj]);
                    }
                }
            }
        }
    }

    return {minSwaps, strategyCount};
}

int main() {
    vector<string> testCases;
    string line;
    while (getline(cin, line)) {
        testCases.push_back(line);
        if (testCases.size() == N) {
            vector<vector<char>> grid(N, vector<char>(N));
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) {
                    grid[i][j] = testCases[i][j];
                }
            }

            int totalMinSwaps = INF;
            int totalStrategyCount = 0;

            for (char target : {'A', 'B', 'C', 'D'}) {
                auto [minSwaps, strategyCount] = aStar(grid, target);
                if (minSwaps < totalMinSwaps) {
                    totalMinSwaps = minSwaps;
                    totalStrategyCount = strategyCount;
                } else if (minSwaps == totalMinSwaps) {
                    totalStrategyCount += strategyCount;
                }
            }

            cout << totalMinSwaps << " " << totalStrategyCount << endl;

            testCases.clear();
        }
    }

    return 0;
}