結果

問題 No.13 囲みたい！
ユーザー こるこる
提出日時 2017-01-07 15:13:17
言語 Java21
(openjdk 21)
結果
AC  
実行時間 131 ms / 5,000 ms
コード長 2,165 bytes
コンパイル時間 3,134 ms
コンパイル使用メモリ 78,264 KB
実行使用メモリ 54,172 KB
最終ジャッジ日時 2024-12-17 16:12:56
合計ジャッジ時間 5,646 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
51,740 KB
testcase_01 AC 66 ms
51,572 KB
testcase_02 AC 50 ms
50,508 KB
testcase_03 AC 131 ms
54,172 KB
testcase_04 AC 117 ms
52,928 KB
testcase_05 AC 99 ms
52,864 KB
testcase_06 AC 123 ms
53,132 KB
testcase_07 AC 93 ms
51,928 KB
testcase_08 AC 102 ms
52,460 KB
testcase_09 AC 117 ms
53,148 KB
testcase_10 AC 57 ms
50,464 KB
testcase_11 AC 96 ms
52,344 KB
testcase_12 AC 53 ms
50,444 KB
testcase_13 AC 78 ms
51,456 KB
testcase_14 AC 74 ms
51,808 KB
testcase_15 AC 48 ms
50,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;
public class No013 {
    
    
    static int[][] map;
    static boolean[][] bool_map;
    static int w;
    static int h;
    static boolean[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        w=Integer.parseInt(st.nextToken());
        h=Integer.parseInt(st.nextToken());
        map=new int[h][w];
        bool_map=new boolean[h][w];
        dp=new boolean[h+1][w+1];
        for(int i=0;i<h;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<w;j++){
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                dfs(i,j,0);
            }
        }System.out.println("impossible");
        
    }
    
    //前回の位置：1:うえ 2:右 3:下 4:左
    static boolean dfs(int tate,int yoko,int course){
        if(dp[tate][yoko]) return false;
        bool_map[tate][yoko]=true;
        if(tate>0 && map[tate-1][yoko]==map[tate][yoko] && course!=1){
            if(bool_map[tate-1][yoko] || dfs(tate-1,yoko,3)){
                System.out.println("possible");
                System.exit(0);
            }
        }if(yoko<w-1 && map[tate][yoko+1]==map[tate][yoko] && course!=2){
            if(bool_map[tate][yoko+1] || dfs(tate,yoko+1,4)){
                System.out.println("possible");
                System.exit(0);
            }
        }if(tate<h-1 && map[tate+1][yoko]==map[tate][yoko] && course!=3){
            if( bool_map[tate+1][yoko] || dfs(tate+1,yoko,1)){
                System.out.println("possible");
                System.exit(0);
            }
        }if(yoko>0 && map[tate][yoko-1]==map[tate][yoko] && course!=4){
            if(bool_map[tate][yoko-1] || dfs(tate,yoko-1,2)){
                System.out.println("possible");
                System.exit(0);
            }
        }
        dp[tate][yoko]=true;
        bool_map[tate][yoko]=false;
        return false;
    }
    
}
0