結果

問題 No.307 最近色塗る問題多くない？
コンテスト
ユーザー nCk_cv
提出日時 2015-11-29 16:19:52
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

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