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.