#include <bits/stdc++.h>
using namespace std;
#define ls u << 1
#define rs u << 1 | 1
#define LL long long
#define int long long
#define PII pair <int, int>
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define i128 __int128
#define pcnt(x) __builtin_popcount(x)
#define mem(a,goal) memset(a, (goal), sizeof(a))
#define rep(x,start,end) for(int x = (start) - ((start) > (end)); x != (end) - ((start) > (end)); ((start) < (end) ? x ++ : x --))
#define aLL(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
const int INF = 998244353;
const int mod = 1e9 + 7;
const int N = 1010;
int g[N][N], dis[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int n, m;
void bfs(int a, int b)
{
    memset(dis, -1, sizeof(dis));
    dis[a][b] = 0;
    queue<PII> q;
    q.push({a, b});
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        for(int i = 0; i < 4; ++ i)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && x < n && y >= 0 && y < m && dis[x][y] == -1 && g[x][y] == 0)
            {
                dis[x][y] = dis[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }    
    cout << dis[n - 1][m - 1] << '\n';
}
void solve()
{
    scanf("%lld%lld", &n, &m);
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            scanf("%lld", &g[i][j]);
    bfs(0, 0);
}

signed main()
{
    int t = 1;
    while (t --) solve();
    return 0;
}

bfs

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>
#include <iomanip>
#include <stack>
#include <bitset>

#define int long long
#define PII pair<int, int> 
#define TLLL tuple<int , int , int>
#define INF 0x3f3f3f3f3f3f3f3f
#define all(v) v.begin() + 1 , v.end()
#define ALL(v) v.begin() , v.end()
#define endl "\n"
using namespace std;

const int N = 1e3 + 10;
int n , m;
int g[N][N] , dist[N][N];
bool st[N][N];

int dx[] = {0 , 1 , 0 , -1} , dy[] = {1 , 0 , -1 , 0};  //四个方向

void bfs(int sx , int sy)
{
    queue<PII> q;
    q.push({sx , sy});
    st[sx][sy] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        int x = t.first , y = t.second;

        for (int i = 0 ; i < 4 ; i ++ )
        {
            int xx = dx[i] + x , yy = dy[i] + y;

            if (xx < 1 || xx > n || yy < 1 || yy > m || g[xx][yy]) continue;
            if (st[xx][yy]) continue;

            st[xx][yy] = true;
            dist[xx][yy] = dist[x][y] + 1;
            q.push({xx , yy});
            
            if (xx == n && yy == m) return ;
        }
    }
}

void solve() 
{   
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++ ) 
        for (int j = 1 ; j <= m ; j ++ )
            cin >> g[i][j];
    
    bfs(1 , 1);

    cout << dist[n][m] << endl;

    return ;
}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    while (T -- ) solve();
    return 0;
}

ref(APA): yxy.千纸雏鸢-My Personal May.https://m.qzcy2.top. Retrieved 2025/9/9.

dijkstra

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>
#include <iomanip>
#include <stack>
#include <bitset>

#define int long long
#define PII pair<int, int> 
#define TLLL tuple<int , int , int>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f
#define all(v) v.begin() + 1 , v.end()
#define ALL(v) v.begin() , v.end()
#define endl "\n"
using namespace std;

const int N = 4e6 + 10;
int e[N] , ne[N] , h[N] , idx , dist[N];
bool st[N];

//链式前向星存图，相关概念可以参考过往文章->图论基础-透析链式前向星
inline void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}

//将二维坐标转化为一维（即：从上到下，从左到右，依次编号为1,2,3,...,n * m）。
inline int transIndex(int a , int b , int m)
{
    return (a - 1) * m + b;
}

//dijkstra
void dijkstra()
{
    memset(st , false , sizeof st);
    memset(dist , inf , sizeof dist);

    priority_queue<PII , vector<PII> , greater<PII> > heap;
    heap.push({0 , 1});

    dist[1] = 0;
    st[1] = true;

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int distance = t.first , index = t.second;

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];

            if (dist[j] > distance + 1)
            {
                dist[j] = distance + 1;
                heap.push({ dist[j] , j});
            }
        }
    }

    return ;
}

//函数本体
void solve()
{
    int n , m;
    cin >> n >> m;
    vector<vector<int> > g(n + 1 , vector<int>(m + 1));
    for (int i = 1 ; i <= n ; i ++ )
        for (int j = 1 ; j <= m ; j ++ )
            cin >> g[i][j];
    
    memset(h , -1 , sizeof h);
    int dx[] = {0 , 1 , 0 , -1} , dy[] = {1 , 0 , -1 , 0};  //四个方向

//坐标转换
    for (int i = 1 ; i <= n ; i ++ )
    {
        for (int j = 1 ; j <= m ; j ++ )
        {
            if (g[i][j]) continue;

            int u = transIndex(i , j , m);

            for (int k = 0 ; k < 4 ; k ++ )
            {
                int x = i + dx[k] , y = j + dy[k];

                if (x < 1 || x > n || y < 1 || y > m || g[x][y]) continue;
                
                int v = transIndex(x , y , m);
                add(u , v) , add(v , u);  //题目描述可以上下左右，即 双向图
            }
        }
    }

    dijkstra();
    int end = transIndex(n , m , m);

    cout << dist[end] << endl;

    return ;
}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T -- ) solve();
    return 0;
}

ref(APA): yxy.千纸雏鸢-My Personal May.https://m.qzcy2.top. Retrieved 2025/9/9.