結果

問題 No.13 囲みたい！
コンテスト
ユーザー こる
提出日時 2017-01-07 15:13:17
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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