結果

問題 No.307 最近色塗る問題多くない？
ユーザー nCk_cvnCk_cv
提出日時 2015-11-29 16:19:52
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,612 bytes
コンパイル時間 2,479 ms
コンパイル使用メモリ 85,420 KB
実行使用メモリ 77,456 KB
最終ジャッジ日時 2024-09-14 05:07:14
合計ジャッジ時間 13,473 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 153 ms
54,364 KB
testcase_01 AC 156 ms
54,228 KB
testcase_02 AC 155 ms
54,008 KB
testcase_03 AC 153 ms
54,092 KB
testcase_04 AC 268 ms
57,132 KB
testcase_05 AC 165 ms
54,512 KB
testcase_06 AC 173 ms
54,404 KB
testcase_07 AC 518 ms
59,864 KB
testcase_08 AC 994 ms
64,220 KB
testcase_09 AC 600 ms
61,448 KB
testcase_10 AC 1,742 ms
71,272 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
import java.util.Map.Entry;
import java.math.*;
import java.awt.geom.*;
import java.io.*;
      
      
public class Main {	
	static char[][] MAP;
	static int[][] COLOR;
	static boolean[][] al;
	static int oa;
	static int ob;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		MAP = new char[h][w];
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				MAP[i][j] = sc.next().charAt(0);
			}
		}
		COLOR = new int[h][w];
		int id = 0;
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				COLOR[i][j] = id++;
			}
		}
		al = new boolean[h][w];
		for(int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++) {
				oa = i;
				ob = j;
				DFS(i,j);
			}
		}
		boolean ok = false;
		char last = 'a';
		int q = sc.nextInt();
		for(int i = 0; i < q; i++) {
			int r = sc.nextInt()-1;
			int c = sc.nextInt()-1;
			char x = sc.next().charAt(0);
			last = x;
			if(ok) {
				continue;
			}
			
			int target = COLOR[r][c];
			
			for(int j = 0; j < h; j++) {
				for(int k = 0; k < w; k++) {
					if(COLOR[j][k] == target)
					MAP[j][k] = x;
				}
			}
			al = new boolean[h][w];
			oa = r;
			ob = c;
			DFS(r,c);
			boolean bad = false;
			IN:for(int j = 0; j < h; j++) {
				for(int k = 0; k < w; k++) {
					if(COLOR[0][0] != COLOR[j][k]) {
						bad = true;
						break IN;
					}
				}
			}
			if(!bad) {
				ok = true;
			}
		}
		if(ok) {
			for(int i = 0; i < h; i++) {
				System.out.print(last);
				for(int j = 1; j < w; j++) {
					System.out.print(" " + last);
				}
				System.out.println();
			}
		}
		else {
			for(int i = 0; i < h; i++) {
				System.out.print(MAP[i][0]);
				for(int j = 1; j < w; j++) {
					System.out.print(" " + MAP[i][j]);
				}
				System.out.println();
			}
		}
	}
	static int[] vx = {0,1,0,-1};
	static int[] vy = {1,0,-1,0};
	static class Data {
		int y;
		int x;
		Data(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	static void DFS(int a, int b) {
		ArrayDeque<Data> queue = new ArrayDeque<Data>();
		queue.addLast(new Data(a,b));
		while(!queue.isEmpty()) {
			Data tmp = queue.pollFirst();
			a = tmp.y;
			b = tmp.x;
			if(a < 0 || b < 0 || a >= MAP.length || b >= MAP[a].length || MAP[a][b] != MAP[oa][ob] || al[a][b]) continue;
			COLOR[a][b] = COLOR[oa][ob];
			al[a][b] = true;
			for(int i = 0; i < 4; i++) {
				int ty = vy[i] + a;
				int tx = vx[i] + b;
				if(ty < 0 || tx < 0 || ty >= MAP.length || tx >= MAP[ty].length || MAP[ty][tx] != MAP[oa][ob] || al[ty][tx]) continue;
				queue.addLast(new Data(ty,tx));
			}
		}
	}

	
	
}
0