求最短通路值

//注：该代码，N和M与题目中的顺序相反
#include<iostream>
#include<vector>
using namespace std;
typedef struct//节点
{
    int x;
    int y;
}node;

int dx[4] = { 1,-1,0,0 };//用于判断上下左右时使用
int dy[4] = { 0,0,1,-1 };//同上
int main()
{
    int M, N;
    cin >> M >> N;
    vector<vector<char>> m(M);//用于储存矩阵
    vector<vector<int>> num(M);//用于储存走到矩阵各点的距离
    for (int x = 0; x < M; x++)//扩容
    {
        m[x].resize(N);
        num[x].resize(N);
    }
    for (int x = 0; x < M; x++)//输入矩阵元素
    {
        getchar();
        for (int y = 0; y < N; y++)
        {
            scanf("%c", &m[x][y]);
        }
    }
    num[0][0] = 1;//走到0，0坐标默认为1
    m[0][0] = '0';//将0，0坐标的元素变'0',以免再次被查找
    int flag = 1;//用于判断是否走到了右下角的点
    node t = { 0,0 };
    vector<node>q;//用于保存路上走到的点的坐标
    q.push_back(t);//将0,0点存到路径动态数组
    while (q.size())//当数组中没有元素时代表没路可走，即停止
    {
        t = q[0];//保存第一个点，以此点开始查找周围
        q.erase(q.begin());//将第一个点从数组中去除，以免下次被调用
        if (t.x == M - 1 && t.y == N - 1)//如果当前的点是右下角的点，就直接输出当前num矩阵中该点的数即可，第一次走到定为最小
        {
            flag = 0;//将flag变0，代表已走到
            cout << num[M - 1][N - 1];
            break;
        }
        for (int i = 0; i < 4; i++)//上下左右查找为'1'的点
        {
            int _x = t.x + dx[i];
            int _y = t.y + dy[i];
            if (_x < 0 || _x >= M || _y < 0 || _y >= N)//坐标越界跳过，执行下一次循环
            {
                continue;
            }
            if (m[_x][_y] == '1')//找到为'1'的点
            {
                m[_x][_y] = '0';//将该点变为'0'防止下次被查找
                num[_x][_y] = num[t.x][t.y] + 1;//令该点对应的num的数变为前一个点的+1
                node new_t = { _x,_y };
                q.push_back(new_t);//因为该坐标可走，所以将新的坐标保存到数组中，做下次查找
            }
        }
    }
    if (flag)//如果找到右下角得点，不能输出，反之输出-1
    {
        cout << -1;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

char G[1001][1001];
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
struct P{
    int x, y, t;
};

int BFS(int n, int m){
    bool vis[n+1][m+1];
    memset(vis, false, sizeof(vis));
    vis[1][1] = true;
    queue<P> q;
    q.push(P{1,1,1});
    while(!q.empty()){
        P p = q.front();
        q.pop();
        if(p.x==n && p.y==m)
            return p.t;
        for(int i=0;i<4;i++){
            int xx = p.x + dir[i][0];
            int yy = p.y + dir[i][1];
            int tt = p.t + 1;
            if(xx>=1 && xx<=n && yy>=1 && yy<=m && G[xx][yy]=='1' && !vis[xx][yy]){
                q.push(P{xx, yy, tt});
                vis[xx][yy] = true;
            }
        }
    }
    return -1;
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>G[i][j];
    cout<<BFS(n,m)<<endl;
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define not !

typedef struct Coordintate {
  int x;
  int y;
} Coord;

// function prototype
void printGrid(int* *grid, const int kRows, const int kCols);
int breadth_first_search_algorithm(int* *grid, const int kRows, const int kCols);

int main(const int argc, const char* const argv[]) {
  int m, n;
  fscanf(stdin, "%d %d\n", &m, &n);
  
  int grid[m][n]; // 逻辑上两维的, 但在内存布局中二维数组是按一维线性连续存储的。
  
  int x, y;
  char str[n + 1];
  for (y = 0; y < m ; ++y) {
    gets(str);
    for (x = 0; x < n; ++x)
      *(*(grid + y) + x) = *(str + x) - 48;
  }
  
  int* rows_of_grid[m]; // 行指针
  for (y = 0; y < m; ++y)
    *(rows_of_grid + y) = grid + y;

  // printGrid(rows_of_grid, m, n);
  fprintf(stdout, "%d", breadth_first_search_algorithm(rows_of_grid, m, n));
  return 0;
}

int breadth_first_search_algorithm(int* *grid, const int kRows, const int kCols) {
  
  Coord q[kRows * kCols]; // 队列的大小由算法的时简复杂度决定，每个单位格最多入队出队一次!
  int front = 0, rear = 0;
  *(q + rear++) = (Coord) {.x = 0, .y = 0};
  **grid = 0; // mark as visited
  
  static const int dirs[] = { 0, -1, 0, 1, 0 };
  
  Coord coord;
  int i, x, y, nx, ny, steps = 0;
  while (front < rear) {
    size_t s = rear - front;
    while (s--) {
      coord = *(q + front++);
      x = coord.x, y = coord.y;
      if (x == kCols - 1 && y == kRows - 1)
        return steps + 1;
      for (i = 0; i < 4; ++i) {
        nx = x + *(dirs + i), ny = y + *(dirs + i + 1);
        if (nx < 0 || ny < 0 || nx == kCols || ny == kRows || !*(*(grid + ny) + nx))
          continue;
        *(q + rear++) = (Coord) {.x = nx, .y = ny};
        *(*(grid + ny) + nx) = 0; // mark as visited
      }
    }
    ++steps;
  }
  
  return -1;
}

void printGrid(int* *grid, const int kRows, const int kCols) {
  int x, y;
  for (y = 0; y < kRows; ++y) {
    for (x = 0; x < kCols; ++x)
      printf("%d ", *(*(grid + y) + x));
    fputc(10, stdout);
  }
}

Java BFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static int m ;
    private static int n ;
    private static int[][] mat;
    public static void main(String[] args) {
        int[][] direcion = {{1,0},{0,1},{-1,0},{0,-1}};
        int res = - 1;
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        mat = new int[m][n];
        for (int i = 0; i < m; i++) {
            String s = sc.next();
            for (int j = 0; j < n; j++) {
                mat[i][j] = s.charAt(j) -'0';
            }
        }
        Queue<Node> queue = new LinkedList<>();
        Node root = new Node(0,0,1);
        queue.offer(root);
        while(!queue.isEmpty()){
            Node p = queue.peek();
            int x = p.x;
            int y = p.y;
            int dis = p.dis;
            if(x == m-1 && y == n - 1){
                res = dis;
                break;
            }
            for (int i = 0; i < direcion.length; i++) {
                int newX = direcion[i][0] + x;
                int newY = direcion[i][1] + y;
                Node temp = new Node(newX,newY,dis+1);
                if(isTrue(temp)){
                    queue.offer(temp);
                    mat[newX][newY] = 0;
                }
            }
            queue.poll();
        }
        System.out.println(res);
    }

    public static class Node{
        private int x;
        private int y;
        private int dis;

        public Node(int x, int y, int dis) {
            this.x = x;
            this.y = y;
            this.dis = dis;
        }
    }


    public static boolean isTrue(Node node){
        int x = node.x;
        int y = node.y;
        if((x<0 || x>=m)||(y<0 || y>=n)) return false;
        if(mat[x][y] == 0) return false;
        return true;
    }
}

# -*- coding: utf-8 -*-
# !/usr/bin/python3
# 解题思路，利用广度优先搜索（BFS）进行遍历，从00到mn位置最少需要几层，就是最短路径的长度
# 判断每层的条件：下标合法不越界，数组中值为1，并且没有被遍历过
# BFS将每层可遍历的元素保存到一个集合中，将该集合作为下次遍历的对象，寻找下一层
# 只到找到mn位置为止，如果找不到就是-1


def bfs(arr, m, n):
    if arr[0][0] == 0:
        return -1

    vst = [[0 for k in range(n)] for k in range(m)]
    qe, steps, vst[0][0] = {(0, 0)}, 1, 1
    while qe:
        tmp = set()
        for x, y in qe:
            if (x, y) == (m - 1, n - 1):
                return steps
            for k, l in ((x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)):
                if 0 <= k < m and 0 <= l < n and arr[k][l] == 1 and vst[k][l] == 0:
                    tmp.add((k, l))
                    vst[k][l] = 1

        steps += 1
        qe = tmp

    return -1


while True:
    try:
        m, n = map(int, input().split())

        arr = []
        for i in range(m):
            s = input()
            tmp = []
            for j in range(n):
                tmp.append(int(s[j]))
            arr.append(tmp)

        print(bfs(arr, m, n))

    except:
        break