結果

問題 No.307 最近色塗る問題多くない？
ユーザー nCk_cvnCk_cv
提出日時 2015-11-29 16:17:45
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 2,611 bytes
コンパイル時間 2,427 ms
コンパイル使用メモリ 87,344 KB
実行使用メモリ 71,380 KB
最終ジャッジ日時 2023-10-12 05:41:05
合計ジャッジ時間 23,715 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 145 ms
53,684 KB
testcase_01 WA -
testcase_02 AC 148 ms
55,428 KB
testcase_03 AC 146 ms
53,732 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 518 ms
61,352 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 TLE -
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);
			if(ok) {
				last = x;
				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]) return;
			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