미로 알고리즘, 너비 우선 검색 자바 구현
23697 단어 알고리즘
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
5 5
1 1 0 1 1
0 1 0 1 0
0 1 1 1 0
0 0 1 1 0
1 0 1 1 1
*
*/
public class BfsTest {
// ,0: , 1:
static int[][] maze;
//
static int m, n;
// ,
static int[] dx = { 1, -1, 0, 0 };
static int[] dy = { 0, 0, 1, -1 };
//
static int[][] dist = new int[100][100];
//
static boolean[][] vstd = new boolean[100][100];
// ,
static List<Point> queue = new ArrayList<>();
/**
* :
* : x >= 0 && y >= 0 && x < m && y < n
* : !vstd[x][y],
* : maze[x][y] == 1
* @param x
* @param y
* @return
*/
static boolean judge(int x, int y) {
return x >= 0 && y >= 0 && x < m && y < n && !vstd[x][y] && maze[x][y] == 1 ;
}
/**
* ,
* @param x
* @param y
*/
public static void bfs(int x, int y) {
if(!judge(x, y)) {
return;
}
queue.add(new Point(x, y, 1));//
dist[x][y] = 1; // 1
vstd[x][y] = true;//
//
for(int i = 0; i < queue.size(); i++) {
Point currP = queue.get(i); //
int currX = currP.x;
int currY = currP.y;
//
for(int j = 0;j < 4;j++) {
int nextX = currX + dx[j];
int nextY = currY + dy[j];
if(judge(nextX, nextY)) { //
int step = currP.step + 1; //
queue.add(new Point(nextX, nextY, step)); //
dist[nextX][nextY] = step; //
vstd[nextX][nextY] = true; //
}
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
m = scan.nextInt();
n = scan.nextInt();
maze = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int t = scan.nextInt();
maze[i][j] = t;
}
}
scan.close();
System.out.println("search: 2, 1");
bfs(2, 1); // ,
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(dist[i][j] + "\t");
}
System.out.println();
}
System.out.println("search: 0, 0");
queue = new ArrayList<>();
vstd = new boolean[100][100];
dist = new int[100][100];
bfs(0, 0); // ,
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(dist[i][j] + "\t");
}
System.out.println();
}
}
}
class Point {
public int x, y, step;
public Point(int x, int y, int step) {
this.x = x;
this.y = y;
this.step = step;
}
}
샘플 입 출력
5 5
1 1 0 1 1
0 1 0 1 0
0 1 1 1 0
0 0 1 1 0
1 0 1 1 1
search: 2, 1
4 3 0 5 6
0 2 0 4 0
0 1 2 3 0
0 0 3 4 0
0 0 4 5 6
search: 0, 0
1 2 0 8 9
0 3 0 7 0
0 4 5 6 0
0 0 6 7 0
0 0 7 8 9
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.