颜色交替最短路径

颜色交替最短路径

class Solution {
    public int[] shortestAlternatingPaths(int n,int[][] redEdges,int[][] blueEdges){
        //建立邻接表，需要保存上一条边的颜色
        List<List<Node>> graph=new ArrayList<List<Node>>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }
        for (int[] e : redEdges) {
            graph.get(e[0]).add(new Node(e[1],0));
        }
        for (int[] e : blueEdges) {
            graph.get(e[0]).add(new Node(e[1],1));
        }
        //创建距离数组
        int[][] dist=new int[n][2];
        for(int i=0;i<n;i++){
            Arrays.fill(dist[i],Integer.MAX_VALUE);
        }
        //通过广度优先
        bfs(graph,dist);
        int[] res=new int[n];
        for(int i=0;i<n;i++){
            res[i]=Math.min(dist[i][0],dist[i][1]);
            if(res[i]==Integer.MAX_VALUE){
                res[i]=-1;
            }
        }
        return res;
    }

    public void bfs(List<List<Node>> graph,int[][] dist){
        //将起点加入队列
        Queue<Node> queue=new LinkedList<Node>();
        dist[0][0]=dist[0][1]=0;
        queue.offer(new Node(0,0));
        queue.offer(new Node(0,1));

        while (!queue.isEmpty()) {
            Node node=queue.poll();
            int start=node.val;int color=node.color;
            for (Node e : graph.get(start)) {
                int v=e.val;int nextColor=e.color;
                if(nextColor!=color&&dist[v][nextColor]>dist[start][color]+1){
                    dist[v][nextColor]=dist[start][color]+1;
                    queue.offer(new Node(v,nextColor));
                }
            }
        }
    }
}
class Node{
    int val;
    int color;
    public Node(int val,int color){
        this.val=val;
        this.color=color;
    }
}

广度优先搜索

import java.io.*;
import java.util.*;
public class Main{

    static int N=110;
    static int[][] g=new int[N][N];
    static int[] dx={0,1,0,-1};
    static int[] dy={1,0,-1,0};
    static boolean[][] vis=new boolean[N][N];
    static int res=Integer.MAX_VALUE;
    public static void main(String[] args)throws IOException{
        BufferedReader cin=new BufferedReader(new InputStreamReader(System.in));
        String[] str=cin.readLine().split(" ");
        int n=Integer.parseInt(str[0]);int m=Integer.parseInt(str[1]);
        for(int i=1;i<=n;i++){
            String[] s=cin.readLine().split(" ");
            for(int j=1;j<=m;j++){
                g[i][j]=Integer.parseInt(s[j-1]);
            }
        }
        Queue<int[]> queue=new LinkedList<int[]>();
        queue.offer(new int[]{1,1,0});
        while(!queue.isEmpty()){
            int[] node=queue.poll();
            int x=node[0];int y=node[1];int cost=node[2];
            vis[x][y]=true;
            if(x==n&&y==m){
                res=Math.min(res,cost);
                break;
            }
            for(int k=0;k<4;k++){
                int a=x+dx[k];int b=y+dy[k];
                if(a<1||a>n||b<1||b>m||g[a][b]==1||vis[a][b]){
                    continue;
                }
                queue.offer(new int[]{a,b,cost+1});
            }
        }
        System.out.println(res);
    }

}

通过距离数组进行广度优先搜索

import java.io.*;
import java.util.*;
public class Main{

    static int N=110;
    static int[][] g=new int[N][N];
    static int[][] d=new int[N][N];

    //通过数组模拟队列
    static node[] queue=new node[N*N];

    static int[] dx={0,1,0,-1};
    static int[] dy={1,0,-1,0};

    public static void main(String[] args)throws IOException{
        BufferedReader cin=new BufferedReader(new InputStreamReader(System.in));
        String[] str=cin.readLine().split(" ");
        int n=Integer.parseInt(str[0]);int m=Integer.parseInt(str[1]);
        for(int i=1;i<=n;i++){
            Arrays.fill(d[i],-1);
        }
        for(int i=1;i<=n;i++){
            String[] s=cin.readLine().split(" ");
            for(int j=1;j<=m;j++){
                g[i][j]=Integer.parseInt(s[j-1]);
            }
        }

        System.out.println(bfs(n,m));
    }

    public static int bfs(int n,int m){
        int hh=0;int tt=0;
        queue[0]=new node(1,1);
        d[1][1]=0;
        while(hh<=tt){
            node t=queue[hh++];
            for(int k=0;k<4;k++){
                int x=t.x+dx[k];int y=t.y+dy[k];
                if(x>=1&&x<=n&&y>=1&&y<=m&&g[x][y]==0&&d[x][y]==-1){
                    d[x][y]=d[t.x][t.y]+1;
                    queue[++tt]=new node(x,y);
                }
            }
        }
        return d[n][m];
    }
}
class node{
    int x,y;
    public node(int x,int y){
        this.x=x;
        this.y=y;
    }
}

数的层次 树中的节点到根节点的距离

import java.util.*;

public class Main{
    static int N=100010;
    static int[] h=new int[N];static int[] e=new int[N];static int[] ne=new int[N];
    static int idx=0;
    //通过数组模拟队列
    static int[] queue=new int[N];
    static int hh=0,tt=-1;
    static int[] d=new int[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int m=sc.nextInt();
        Arrays.fill(h,-1);
        Arrays.fill(d,-1);
        for(int i=0;i<m;i++){
            int a=sc.nextInt();int b=sc.nextInt();
            add(a,b);
        }
        System.out.println(bfs(n));
    }

    public static int bfs(int n){
        queue[++tt]=1;
        d[1]=0;
        while(hh<=tt){
            int t=queue[hh++];
            for(int i=h[t];i!=-1;i=ne[i]){
                int j=e[i];
                if(d[j]==-1){
                    d[j]=d[t]+1;
                    queue[++tt]=j;
                }
            }
        }
        return d[n];
    }

    public static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }

}

insert(int a,int b)之前进行初始化Arrays.fill(h,-1);

import java.util.*;

public class Main{
    static int N=100010;
    static int[] h=new int[N];static int[] e=new int[N];
    static int[] ne=new int[N];
    static int idx=0;
    static int[] queue=new int[N];
    static int tt=-1,hh=0;
    static int[] deg=new int[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int m=sc.nextInt();      
        Arrays.fill(h,-1);
        for(int i=0;i<m;i++){
            int a=sc.nextInt();int b=sc.nextInt();
            add(a,b);
            deg[b]++;
        }
        if(bfs(n)){
            for(int i=0;i<n;i++){
                System.out.print(queue[i]+" ");
            }
            System.out.println();
        }else{
            System.out.println("-1");
        }
    }

    public static boolean bfs(int n){
        //将所有的入度为0节点加入队列
        for(int i=1;i<=n;i++){
            if(deg[i]==0){
                queue[++tt]=i;
            }
        }
        while(hh<=tt){
            int t=queue[hh++];
            for(int i=h[t];i!=-1;i=ne[i]){
                int j=e[i];
                deg[j]--;
                if(deg[j]==0){
                    queue[++tt]=j;
                }
            }
        }
        return tt==n-1;
    }

    public static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}