题解 | 太阳之华

import java.util.*;

public class Main{
    static int N = 2005;
    public static class pos{
        int x;
        int y;
        pos(){}
        pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static boolean check(int n, int m, int[][] a, int cntb){
        Queue<pos> q = new LinkedList<pos>();
        int[] dx = {-1,0,0,1};
        int[] dy = {0,-1,1,0};
        int[][] tag = new int[n+5][m+5];
        int[][] bel = new int[n+5][m+5];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                tag[i][j] = 0;
                bel[i][j] = 0;
            }
        int cnt = 0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(a[i][j] == 1 && bel[i][j] == 0){
                    //System.out.println(i+" "+j);
                    int res = 0;
                    cnt++;
                    bel[i][j] = cnt;
                    pos now = new pos(i,j);
                    q.offer(now);
                    while(q.size() > 0){
                        pos tmp = q.peek();
                        q.poll();
                        for(int k=0;k<4;k++){
                            int nx = tmp.x + dx[k], ny = tmp.y + dy[k];
                            //System.out.println(nx + " " + ny);
                            if(nx < 1 || nx > n) continue;
                            if(ny < 1 || ny > m) continue;
                            if(a[nx][ny] == 1 && bel[nx][ny] == 0){
                                bel[nx][ny] = bel[tmp.x][tmp.y];
                                pos nxt = new pos(nx,ny);
                                q.offer(nxt);
                            }
                            else if(a[nx][ny] == 0 && tag[nx][ny] != bel[tmp.x][tmp.y]){
                                tag[nx][ny] = bel[tmp.x][tmp.y];
                                res++;
                                //System.out.println(tmp.x+" "+tmp.y+" "+nx+" "+ny+" "+tag[nx][ny]);
                            }
                        }
                    }
                    if(res == cntb) return true;
                }
        return false;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T-- > 0){
            int n = in.nextInt();
            int m = in.nextInt();
            int cntb = 0;
            String[] s = new String[n+5];
            int[][] a = new int[n+5][m+5];
            s[0] = in.nextLine();
            for(int i=1;i<=n;i++){
                s[i] = in.nextLine();
                for(int j=1;j<=m;j++){
                    if(s[i].charAt(j-1) == '#') a[i][j] = 1;
                    else{
                        a[i][j] = 0;
                        cntb ++;
                    }
                }
            }
            if(cntb == n*m){
                System.out.println("Blue");
            }
            else if(check(n, m, a, cntb)){
                System.out.println("Red");
            }
            else{
                System.out.println("Draw");
            }
        }
    }
}