미로 알고리즘, 너비 우선 검색 자바 구현

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	

좋은 웹페이지 즐겨찾기