広さ優先で迷路を探索する最短経路の歩き方!
2051 ワード
自分の前のブログを引用します:DFSで実現した迷路を歩いて、ここでBFSでもう一度歩きます!
最近迷宮の中に迷い込んでいるような気がします!恐ろしい...
コードを言わないで、問題があったら大神たちに指摘してほしい!謙虚に受け入れる!
最近迷宮の中に迷い込んでいるような気がします!恐ろしい...
コードを言わないで、問題があったら大神たちに指摘してほしい!謙虚に受け入れる!
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
* BFS
*
* */
public class bfsmigong {
static int p;// x
static int q;// y
static int startx;// x
static int starty;// y
static int[][] book;// ,
static int n;
static int m;
static int[][] a;
static int[][] d=new int[51][51];
static int next[][] = new int[][] { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, };
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
a = new int[51][51];
book = new int[51][51];
for (int i = 1; i <= n; i++) {// , 0 0 ,
for (int j = 1; j <= m; j++) {
a[i][j] = sc.nextInt();
}
}
// sop(a, m, n);
startx = sc.nextInt();
starty = sc.nextInt();
p = sc.nextInt();
q = sc.nextInt();
note temp = new note(startx, starty);
Queue queue = new LinkedList();
queue.offer(temp);
book[startx][starty] = 1;// 1, 。
int flag = 0;
int sum = 0;
int tx, ty;
while (!queue.isEmpty()) {
note local = queue.remove();
for (int k = 0; k <= 3; k++) {
tx = local.x + next[k][0];
ty = local.y + next[k][1];
note nbr = new note(tx, ty);
if (nbr.x < 1 || nbr.y < 1 || nbr.x > n || nbr.y > m) {
continue;
}
if (a[nbr.x][nbr.y] == 0 && book[nbr.x][nbr.y] == 0) {
book[nbr.x][nbr.y] = 1;
queue.offer(nbr);
d[tx][ty]=d[local.x][local.y]+1;
}
if (tx == p && ty == q) {
flag = 1;
break;
}
}
if (flag == 1) {
break;
}
}
System.out.println(d[p][q]);
}
}
class note {
int x;
int y;
int s;
note(int x, int y) {
this.x = x;
this.y = y;
}
}
/*
*
*
*
*/
テストデータ:5 4
0 0 1 0
0 0 1 0
0 0 0 0
0 1 0 0
0 0 0 1
1 1 4 3
出力:7