結果

問題 No.13 囲みたい！
コンテスト
ユーザー Grenache
提出日時 2016-05-28 18:40:50
言語 Java
(openjdk 23)
結果
AC  
実行時間 266 ms / 5,000 ms
コード長 2,015 bytes
コンパイル時間 4,025 ms
コンパイル使用メモリ 78,108 KB
実行使用メモリ 48,108 KB
最終ジャッジ日時 2024-10-13 10:53:44
合計ジャッジ時間 7,970 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;


public class Main_yukicoder13 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        int w = sc.nextInt();
        int h = sc.nextInt();

        int[][] field = new int[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
            	field[i][j] = sc.nextInt();
            }
        }

        boolean[][] used = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
            	if (used[i][j]) {
            		continue;
            	}

            	Deque<Integer> qx = new ArrayDeque<>();
            	Deque<Integer> qy = new ArrayDeque<>();
            	Deque<Integer> qpx = new ArrayDeque<>();
            	Deque<Integer> qpy = new ArrayDeque<>();
            	qy.push(i);
            	qx.push(j);
            	qpy.push(-1);
            	qpx.push(-1);
            	used[i][j] = true;

            	while (!qx.isEmpty()) {
            		int x = qx.pop();
            		int y = qy.pop();
            		int px = qpx.pop();
            		int py = qpy.pop();

            		for (int k = 0; k < dx.length; k++) {
            			int nx = x + dx[k];
            			int ny = y + dy[k];
            			if (nx < 0 || nx >= w || ny < 0 || ny >= h) {
            				continue;
            			}
            			if (nx == px && ny == py) {
            				continue;
            			}
            			if (field[ny][nx] != field[i][j]) {
            				continue;
            			}

            			if (used[ny][nx]) {
            				System.out.println("possible");

            				sc.close();
            				return;
            			}

            			qx.push(nx);
            			qy.push(ny);
            			qpx.push(x);
            			qpy.push(y);
            			used[ny][nx] = true;
            		}
            	}
            }
        }

        System.out.println("impossible");

        sc.close();
    }
}
0