結果

問題 No.13 囲みたい！
ユーザー こるこる
提出日時 2017-01-07 15:13:17
言語 Java21
(openjdk 21)
結果
AC  
実行時間 93 ms / 5,000 ms
コード長 2,165 bytes
コンパイル時間 3,430 ms
コンパイル使用メモリ 74,556 KB
実行使用メモリ 52,900 KB
最終ジャッジ日時 2023-08-22 16:15:25
合計ジャッジ時間 5,318 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
49,184 KB
testcase_01 AC 41 ms
49,168 KB
testcase_02 AC 42 ms
49,176 KB
testcase_03 AC 92 ms
51,984 KB
testcase_04 AC 86 ms
52,004 KB
testcase_05 AC 92 ms
52,900 KB
testcase_06 AC 79 ms
52,072 KB
testcase_07 AC 79 ms
52,164 KB
testcase_08 AC 92 ms
52,352 KB
testcase_09 AC 93 ms
51,796 KB
testcase_10 AC 55 ms
50,532 KB
testcase_11 AC 90 ms
52,252 KB
testcase_12 AC 47 ms
49,212 KB
testcase_13 AC 71 ms
50,440 KB
testcase_14 AC 71 ms
50,240 KB
testcase_15 AC 43 ms
49,248 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