宽度优先搜索算法-BreadthFirstSearch(BFS)

左手的ㄟ右手 2024-04-06 10:26 95阅读 0赞

package com.xch3.wide;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    public class Main1 {
    
    	// 学霸的迷宫：BFS（宽搜）
    	public static String f1(char[][] table) {
    		List<Node> list = new ArrayList<Node>();
    		list.add(new Node(0, 0, ""));// 初始化
    		table[0][0] = 1;// 标记防死循环
    		int x, y;
    		String str;
    		while (list.size() != 0) {
    			x = list.get(0).x;
    			y = list.get(0).y;
    			str = list.get(0).s;
    			if (x == table.length - 1 && y == table[0].length - 1) {// 循环出口
    				return str;
    			}
    			if (x < table.length - 1 && table[x + 1][y] == '0') {// 下
    				list.add(new Node(x + 1, y, str + "D"));
    				table[x + 1][y] = '1';
    			}
    			if (y>0 && table[x][y - 1] == '0') {// 左
    				list.add(new Node(x, y - 1, str + "L"));
    				table[x][y - 1] = '1';
    			}
    			if (y<table[0].length-1 && table[x][y + 1] == '0') {// 右
    				list.add(new Node(x, y + 1, str + "R"));
    				table[x][y + 1] = '1';
    			}
    			if (x>0 && table[x - 1][y] == '0') {// 上
    				list.add(new Node(x - 1, y, str + "U"));
    				table[x - 1][y] = '1';
    			}
    			list.remove(0);
    		}
    		return null;// 无路径
    	}
    
    	static class Node {
    		int x, y;// 节点的坐标
    		String s;// 节点的属性，如：步数或路径等
    
    		public Node(int x, int y, String s) {
    			super();
    			this.x = x;
    			this.y = y;
    			this.s = s;
    		}
    
    		@Override
    		public String toString() {
    			return "Node [x=" + x + ", y=" + y + ", s=" + s + "]";
    		}
    	}
        
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt(), m = sc.nextInt();// n行m列迷宫
    		char[][] table = new char[n][m];
    		for (int i = 0; i < table.length; i++) {
    			table[i] = sc.next().toCharArray();
    		}
    		String str = f1(table);
    		System.out.println(str.length());
    		System.out.println(str.toString());
            
    	}
    
    }