C++代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility> // 确保 pair 的支持
using namespace std;

const int MAXN = 1005;

int main() {
    ios::sync_with_stdio(false); // 加速输入输出
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m));
    pair<int, int> start = {-1, -1}, end_point = {-1, -1};
    
    // 读取矩阵并找到起点和终点
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
            if (matrix[i][j] == 1) {
                start = {i, j};
            } else if (matrix[i][j] == 2) {
                end_point = {i, j};
            }
        }
    }
    
    // 检查是否找到起点和终点
    if (start == pair<int, int>(-1, -1) || end_point == pair<int, int>(-1, -1)) {
        cerr << "未找到起点或终点！" << endl;
        return 1;
    }
    
    // BFS初始化
    queue<pair<pair<int, int>, int>> q;
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    vector<vector<pair<int, int>>> prev(n, vector<pair<int, int>>(m, {-1, -1}));
    
    q.push({{start.first, start.second}, 0});
    visited[start.first][start.second] = true;
    
    // 进行BFS
    bool found = false;
    int steps = 0;
    while (!q.empty() && !found) {
        pair<pair<int, int>, int> current_step = q.front();
        q.pop();
        int x = current_step.first.first;
        int y = current_step.first.second;
        int step = current_step.second;
        
        // 检查是否到达终点
        if (x == end_point.first && y == end_point.second) {
            steps = step;
            found = true;
            break;
        }
        
        // 四个方向
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 检查新坐标是否合法
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && 
                (matrix[nx][ny] == 4 || matrix[nx][ny] == 2)) {
                visited[nx][ny] = true;
                prev[nx][ny] = {x, y};
                q.push({{nx, ny}, step + 1});
            }
        }
    }
    
    // 输出步数
    cout << steps << endl;
    
    // 如果步数是偶数，输出路径
    if (steps % 2 == 0) {
        vector<pair<int, int>> path;
        int x = end_point.first, y = end_point.second;
        while (x != start.first || y != start.second) {
            path.push_back({x + 1, y + 1}); // 转换为1-based坐标
            pair<int, int> p = prev[x][y];
            x = p.first;
            y = p.second;
        }
        path.push_back({start.first + 1, start.second + 1});
        reverse(path.begin(), path.end());
        
        // 输出路径
        for (auto& p : path) {
            cout << "(" << p.first << "," << p.second << ")" << endl;
        }
    }
    
    return 0;
}