题解

题目分析

我们需要判断给定的初始棋盘是否能在指定步数内通过合法移动（将相邻数字移动到空缺位'X'）转变为目标棋盘。如果可以，输出最优解步数；否则，输出不可解。

方法思路

1. 输入处理：读取棋盘维度D、最大步数N、初始棋盘和目标棋盘。
2. 可行性判断：计算初始棋盘和目标棋盘的逆序数，若奇偶性不同则直接不可解。
3. 广度优先搜索(BFS)：从初始状态出发，探索所有可能的移动，直到找到目标状态或超出步数限制。
4. 状态表示：使用字符串表示棋盘状态，便于比较和存储。
5. 移动模拟：每次移动将'X'与相邻数字交换，生成新状态。

解决代码

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <sstream>
#include <cstdio>

using namespace std;

struct BoardState {
    vector<vector<string> > board;
    int steps;
    int x_row, x_col;
};

// 检查两个棋盘是否相同
bool isSameBoard(const vector<vector<string> >& a, const vector<vector<string> >& b) {
    for (size_t i = 0; i < a.size(); ++i) {
        for (size_t j = 0; j < a[i].size(); ++j) {
            if (a[i][j] != b[i][j]) {
                return false;
            }
        }
    }
    return true;
}

// 计算逆序数
int calculateInversions(const vector<string>& flatBoard) {
    int inv = 0;
    for (size_t i = 0; i < flatBoard.size(); ++i) {
        if (flatBoard[i] == "X") continue;
        for (size_t j = i + 1; j < flatBoard.size(); ++j) {
            if (flatBoard[j] == "X") continue;
            if (flatBoard[i] > flatBoard[j]) {
                inv++;
            }
        }
    }
    return inv;
}

// 检查是否可解
bool isSolvable(const vector<vector<string> >& start, const vector<vector<string> >& goal, int D) {
    vector<string> flatStart, flatGoal;
    for (int i = 0; i < D; ++i) {
        for (int j = 0; j < D; ++j) {
            flatStart.push_back(start[i][j]);
            flatGoal.push_back(goal[i][j]);
        }
    }
    
    int invStart = calculateInversions(flatStart);
    int invGoal = calculateInversions(flatGoal);
    
    if (D % 2 == 1) {
        return (invStart % 2) == (invGoal % 2);
    } else {
        int startXRow = 0, goalXRow = 0;
        for (int i = 0; i < D; ++i) {
            for (int j = 0; j < D; ++j) {
                if (start[i][j] == "X") startXRow = i;
                if (goal[i][j] == "X") goalXRow = i;
            }
        }
        return ((invStart + startXRow) % 2) == ((invGoal + goalXRow) % 2);
    }
}

// 查找X的位置
void findX(const vector<vector<string> >& board, int& x_row, int& x_col) {
    for (size_t i = 0; i < board.size(); ++i) {
        for (size_t j = 0; j < board[i].size(); ++j) {
            if (board[i][j] == "X") {
                x_row = i;
                x_col = j;
                return;
            }
        }
    }
}

// 将棋盘转换为字符串
string boardToString(const vector<vector<string> >& board) {
    string s;
    for (size_t i = 0; i < board.size(); ++i) {
        for (size_t j = 0; j < board[i].size(); ++j) {
            s += board[i][j] + " ";
        }
    }
    return s;
}

// BFS搜索最短路径
int solvePuzzle(const vector<vector<string> >& start, const vector<vector<string> >& goal, int maxSteps, int D) {
    if (!isSolvable(start, goal, D)) {
        return -1;
    }
    
    queue<BoardState> q;
    map<string, bool> visited;
    
    BoardState initial;
    initial.board = start;
    initial.steps = 0;
    findX(start, initial.x_row, initial.x_col);
    q.push(initial);
    visited[boardToString(start)] = true;
    
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    while (!q.empty()) {
        BoardState current = q.front();
        q.pop();
        
        if (isSameBoard(current.board, goal)) {
            return current.steps;
        }
        
        if (current.steps >= maxSteps) {
            continue;
        }
        
        for (int i = 0; i < 4; ++i) {
            int newX = current.x_row + dirs[i][0];
            int newY = current.x_col + dirs[i][1];
            
            if (newX >= 0 && newX < D && newY >= 0 && newY < D) {
                vector<vector<string> > newBoard = current.board;
                swap(newBoard[current.x_row][current.x_col], newBoard[newX][newY]);
                
                string newBoardStr = boardToString(newBoard);
                if (!visited[newBoardStr]) {
                    visited[newBoardStr] = true;
                    BoardState next;
                    next.board = newBoard;
                    next.steps = current.steps + 1;
                    next.x_row = newX;
                    next.x_col = newY;
                    q.push(next);
                }
            }
        }
    }
    
    return -1;
}

int main() {
    string line;
    while (getline(cin, line)) {
        if (line.substr(0, 5) == "START") {
            int D, N;
            sscanf(line.c_str(), "START %d %d", &D, &N);
            
            // 读取初始棋盘
            vector<vector<string> > startBoard(D, vector<string>(D));
            for (int i = 0; i < D; ++i) {
                getline(cin, line);
                istringstream iss(line);
                for (int j = 0; j < D; ++j) {
                    iss >> startBoard[i][j];
                }
            }
            
            // 读取目标棋盘
            vector<vector<string> > goalBoard(D, vector<string>(D));
            for (int i = 0; i < D; ++i) {
                getline(cin, line);
                istringstream iss(line);
                for (int j = 0; j < D; ++j) {
                    iss >> goalBoard[i][j];
                }
            }
            
            getline(cin, line); // 读取END
            
            int minSteps = solvePuzzle(startBoard, goalBoard, N, D);
            if (minSteps != -1) {
                cout << "SOLVABLE WITHIN " << minSteps << " MOVES" << endl;
            } else {
                cout << "NOT SOLVABLE WITHIN " << N << " MOVES" << endl;
            }
        }
    }
    return 0;
}

代码解释

1. BoardState结构体：存储当前棋盘状态、步数和'X'的位置。
2. isSameBoard函数：比较两个棋盘是否相同。
3. calculateInversions函数：计算棋盘的逆序数，用于判断可解性。
4. isSolvable函数：根据逆序数奇偶性判断是否可解。
5. findX函数：查找'X'的位置。
6. boardToString函数：将棋盘转换为字符串，用于状态记录。
7. solvePuzzle函数：BFS搜索最短路径。
8. main函数：处理输入，调用求解函数并输出结果。

该解决方案通过BFS搜索最短路径，并结合逆序数判断可解性，确保在合理时间内解决问题。