Java版的广度优先寻路（BFS+并查集思想）

2020-12-13 16:36

阅读：418

标签：pac 广度优先 string sch div ast char private ring

import java.util.Deque;
import java.util.LinkedList;


class node{
    int x;
    int y;
}

class Solution{
    private int dir[][]=new int[][] {{0,-1},{-1,0},{0,1},{1,0}};
    private node parentx[][];
    private int Count[][];
    private boolean used[][];
    private node start=new node();
    private node end=new node();
    private Deque queue=new LinkedList();
    private node temp;
    private boolean flag=false;
    public boolean isCheckMove(String[] map,node start) {
        return start.x>=0&&start.x=0&&start.ymap[start.x].length();
    }
    public boolean printPath(String[] map) {
        while(parentx[temp.x][temp.y].x!=temp.x||parentx[temp.x][temp.y].y!=temp.y) {
            System.out.print(map[temp.x].charAt(temp.y)+"->");
            temp=parentx[temp.x][temp.y];         
        }
        System.out.println(map[temp.x].charAt(temp.y));
        return true;
    }
    public int dfs(String[] map,node start) {
        
        queue.offer(start);
        used[start.x][start.y]=true;
        Count[start.x][start.y]=1;
        
        while(!queue.isEmpty()) {
            start=queue.pop();
            for(int i=0;ii) {
                temp=new node();
                temp.x=start.x+dir[i][0];
                temp.y=start.y+dir[i][1];
                 if(temp.x==end.x&&temp.y==end.y) {
                     flag=true;
                     queue.addLast(temp);
                     parentx[temp.x][temp.y]=start;
                     Count[temp.x][temp.y]=Count[start.x][start.y]+1;
                     used[temp.x][temp.y]=true;
                    break;
                }
                if(isCheckMove(map,temp)&&!used[temp.x][temp.y]) {
                     queue.addLast(temp);
                     parentx[temp.x][temp.y]=start;
                     Count[temp.x][temp.y]=Count[start.x][start.y]+1;
                     used[temp.x][temp.y]=true;
                }
            }
            if(flag) {
                break;
            }
        }
        return Count[temp.x][temp.y];
    }
    
    public boolean nums(String map[]) {
        queue.clear();
        parentx=new node[map.length][map[0].length()];
        Count=new int[map.length][map[0].length()];
        used=new boolean[map.length][map[0].length()];
        for(int i=0;ii) {
            for(int j=0;jj) {
                used[i][j]=false;
                Count[i][j]=0;
                node tmp=new node();
                tmp.x=i;
                tmp.y=j;
                parentx[i][j]=tmp;
                if(map[i].charAt(j)==‘#‘) {
                    end.x=i;
                    end.y=j;
                }
                if(map[i].charAt(j)==‘@‘) {
                    start.x=i;
                    start.y=j;
                }
            }
        }
        System.out.println(dfs(map,start));
        printPath(map);
        return true;
    }
}


public class First{
     public static void main(String[] args) {
      Solution space = new Solution();
      String map[]= {"****","@***","&&&&","&&&&","**"};
      space.nums(map);
      for(String str:map) {
            System.out.println(str);
        }
    }
}

标签：pac 广度优先 string sch div ast char private ring

原文地址：https://www.cnblogs.com/z2529827226/p/11620972.html

上一篇：[转]Network flow monitoring with Open vSwitch

下一篇：Java 之 Response 发送验证码案例

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Java版的广度优先寻路（BFS+并查集思想）
文章链接：http://soscw.com/essay/36322.html

亲，登录后才可以留言！

Java版的广度优先寻路（BFS+并查集思想）

评论

热门文章

推荐文章

最新文章

置顶文章