黑白染色棋子

    xiaoxiao2021-03-25  85

    

    package xj;

    import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;

    public class RanColor1 {  static int D, B,T;  static int map[][];  static int color[];      static class Node {   int x;  }

     static Node[] queue;  static boolean flag;

     public static void main(String[] args) throws FileNotFoundException {   /* Scanner sc=new Scanner(System.in); */   Scanner sc = new Scanner(new File("src/RanColor"));   T=0;   while (sc.hasNext()) {    D = sc.nextInt();    B = sc.nextInt();    map = new int[D + 1][D + 1];    color = new int[D+1];// 0,1W,2B    queue=new Node[D];    /*if (D == 0 && B == 0) {     break;    }*/    for (int i = 0; i < B; i++) {     int a = sc.nextInt();     int b = sc.nextInt();     map[a][b] = 1;     map[b][a] = 1;    }    flag = true;    T++;    bfs(1);    if (!flag) {     System.out.println("#"+T+" "+"-1");    } else {     int w=0;     for (int i = 1; i < D+1; i++) {      if(color[i]==1){w++;}     }     System.out.print("#"+T+" "+w);     for (int i = 1; i < D+1; i++) {      if(color[i]==1){System.out.print(" "+i);}     }     System.out.println();    }// 记得正确输出   }  }

     private static void bfs(int step) {   int head = 0;   int tail = 1;   Node n1 = new Node();   n1.x = step;   queue[head] = n1;   color[step] = 1;   while(head<tail){    for (int i = 1; i < D + 1; i++) {     int a = queue[head].x;     if (map[a][i] == 1 && map[i][a] == 1) {      if (color[a] == color[i]) {flag=false;return;}      if(color[i]==0){       Node n2=new Node();       n2.x=i;       queue[tail]=n2;       tail++;       if(color[a]==1){color[i]=2;}       if(color[a]==2){color[i]=1;}      }     }    }    head++;   }     }

    }

    //

    2 1 2 1

    4 3 1 2 2 3 3 4

    5 5 1 2 2 3 3 4 4 5 5 1

    6 9 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6

    4 3 1 2 2 3 4 3

    4 4 1 2 1 3 1 4 2 3

    11 10 1 2 1 3 3 4 4 5 5 10 10 11 9 8 9 4 8 6 6 4

    //

    #1 1 1 #2 2 1 3 #3 -1 #4 3 1 2 3 #5 2 1 3 #6 -1 #7 4 1 4 8 10

    转载请注明原文地址: https://ju.6miu.com/read-14525.html

    最新回复(0)