题目描述

给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。

最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。

数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。

输入格式

第一行包含两个整数n和m。

接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

8

算法1

(BFS) $O(搜着瞧)$

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std ;

const int N = 110 ;

queue < int > qx ; // x轴
queue < int > qy ; // y轴

int n , m ;
int t[N][N] ; // 原点到某点的距离
int g[N][N] ;
int dx[5] = { 0 , -1 , 1 , 0 , 0 } ;
int dy[5] = { 0 , 0 , 0 , -1 , 1 } ;

void BFS ( ) {

    int ass = 0 ; // 记录上一步的距离
    qx.push ( 1 ) ;
    qy.push ( 1 ) ;
    g[1][1] = 1 ;

    while ( !qx.empty ( ) ) { 

        for ( int i = 1 ; i <= 4 ; i ++ ) {

            int nx = dx[i] + qx.front ( ) ;
            int ny = dy[i] + qy.front ( ) ;

            if ( g[nx][ny] == 0 && nx >= 1 && ny >= 1 && ny <= m && nx <= n ) {

                t[nx][ny] = ass + 1 ; 
                g[nx][ny] = 1 ; // 标记
                qx.push ( nx ) ;
                qy.push ( ny ) ;

            }

            if ( nx == n && ny == m ) {

                cout << t[nx][ny] ;
                return ;

            }

        }

        qx.pop ( ) ;
        qy.pop ( ) ;
        ass = t[qx.front ( )][qy.front ( )] ; // 记录上个点的距离

    }

}

int main ( ) {

    cin >> n >> m ;
    for ( int i = 1 ; i <= n ; i ++ )
        for ( int j = 1 ; j <= m ; j ++ ) 
            cin >> g[i][j] ;

    BFS ( ) ;

    return 0 ;

}