\color{Red}{走迷宫——详细解析——三种语言}
这里附带打个广告——————我做的所有的题解
思路
所有二维网格图相关的位移——偏移量矢量数组——试判法
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i ++ )
int x = t.first + dx[i], y = t.second + dy[i];
java 方法一:手写数组
import java.util.*;
class Pii {
int x, y;
public Pii(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int N = 110;
static int g[][] = new int [N][N];
static int d[][] = new int [N][N];
static Pii q[] = new Pii [N*N];
static int n, m;
public static int bfs() {
int hh = 0, tt = 0;
int [] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
q[0] = new Pii(0, 0);
d[0][0] = 0;
while (hh <= tt) {
Pii t = q[hh++];
for(int i=0; i<4; i++) {
int x = t.x + dx[i];
int y = t.y + dy[i];
if (x>=0 && x<n && y>=0 && y<m && g[x][y]==0 && d[x][y]==-1){
q[++tt] = new Pii(x, y);
d[x][y] = d[t.x][t.y] + 1;
}
}
}
return d[n-1][m-1];
}
public static void main(String [] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i=0; i<n; i++)
for (int j=0; j<m; j++) {
g[i][j] = sc.nextInt();
d[i][j] = -1;
}
System.out.println(bfs());
}
}
java 方法二:调用容器
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
public class Main {
static int N = 110, n, m;
static int[][] path = new int[N][N];
static int[][] d = new int[N][N];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static LinkedList<PII> q = new LinkedList<>();
static class PII {
int x, y;
public PII(int x, int y) {
this.x = x;
this.y = y;
}
}
static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static void bfs() {
q.add(new PII(0, 0));
d[0][0] = 0;
while (!q.isEmpty()) {
PII t = q.remove();
for (int i = 0; i < 4; i++) {
int a = t.x + dx[i], b = t.y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && d[a][b] == -1 && path[a][b] == 0) {
d[a][b] = d[t.x][t.y] + 1;
q.add(new PII(a, b));
}
}
}
}
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
for (int i = 0; i < n; i++) {
Arrays.fill(d[i], -1);
String[] s2 = br.readLine().split(" ");
for (int j = 0; j < m; j++) {
path[i][j] = Integer.parseInt(s2[j]);
}
}
bfs();
System.out.println(d[n - 1][m - 1]);
}
}
方法一:stl队列的使用
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair <int,int> pii;
const int N = 110;
int g[N][N], d[N][N];
int n, m;
int bfs()
{
queue<pii> q;
q.push({0,0});
memset(d, -1, sizeof (d));
d[0][0] = 0;
while(!q.empty())
{
pii t = q.front();
q.pop();
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for(int i=0; i<4; i++)
{
int x = dx[i] + t.first, y = dy[i] + t.second;
if(x>=0 && x<n && y>=0 && y<m && d[x][y] == -1 && g[x][y] == 0)
{
d[x][y] = d[t.first][t.second] + 1;
q.push({x,y});
}
}
}
return d[n-1][m-1];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
scanf("%d", &g[i][j]);
cout << bfs();
return 0;
}
方法二: python3代码(数组模拟队列)
N = 110
g = [[0] * N for i in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
d = [[-1] * N for i in range(N)]
q = []
def bfs():
hh, tt = 0, 0
q.append((0,0))
d[0][0] = 0
while hh <= tt:
a, b = q[hh]
hh += 1
for i in range(4):
x = dx[i] + a
y = dy[i] + b
if 0 <= x < n and 0 <= y < m and d[x][y] == -1 and g[x][y] == 0:
d[x][y] = d[a][b] + 1
q.append((x,y))
tt += 1
return d[n-1][m-1]
if __name__ == '__main__':
n, m = map(int, input().split())
for i in range(n):
g[i][0:m+1] = map(int, input().split())
print(bfs())
方法三:数组模拟队列
using namespace std;
typedef pair <int,int> pii;
const int N = 110;
int g[N][N], d[N][N];
pii q[N*N];
int n, m;
int bfs()
{
q[0] = {0,0};
memset(d, -1, sizeof(d));
d[0][0] = 0;
int hh = 0, tt = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while(hh<=tt)
{
pii t = q[hh++];
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 && d[x][y] == -1 && g[x][y]==0)
{
d[x][y] = d[t.first][t.second] + 1;
q[++tt] = {x,y};
}
}
}
return d[n-1][m-1];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
scanf("%d", &g[i][j]);
cout << bfs() << endl;
return 0;
}