结果

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 10;
int n, m;
bool obstacle[MAXN + 1][MAXN + 1];
int dist_to[MAXN + 1][MAXN + 1]; 
int dist_from[MAXN + 1][MAXN + 1]; 
int dx[] = {-1, 1, 0, 0}; 
int dy[] = {0, 0, -1, 1};
void bfs(int startX, int startY, int dist[MAXN + 1][MAXN + 1]) {
    queue<pair<int, int>> q;
    q.push({startX, startY});
    dist[startX][startY] = 0;
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && !obstacle[nx][ny] && dist[nx][ny] == INT_MAX) {
                q.push({nx, ny});
                dist[nx][ny] = dist[x][y] + 1;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(obstacle, 0, sizeof(obstacle));
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        obstacle[x][y] = true;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dist_to[i][j] = INT_MAX;
            dist_from[i][j] = INT_MAX;
        }
    }
    bfs(1, 1, dist_to);
    bfs(n, n, dist_from);
    int max_diff = 0;
    bool reachable = false;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dist_to[i][j] != INT_MAX && dist_from[i][j] != INT_MAX) {
                int total_dist = dist_to[i][j] + dist_from[i][j];
                max_diff = max(max_diff, total_dist);
                reachable = true;
            }
        }
    }
    if (!reachable) {
        cout << 0 << endl;
    } else {
        cout << max_diff << endl;
    }
    
    return 0;
}