#4905 (Java) No.86 TVザッピング(2)

• 問題: No.86 TVザッピング(2)
• ユーザー: scache
• 提出日時: 2014-12-06 21:58:19
• 言語: Java (openjdk 23)
• 結果: WA
• 実行時間: -
• コード長: 2,294 bytes
• コンパイル時間: 3,513 ms
• コンパイル使用メモリ: 77,924 KB
• 実行使用メモリ: 41,764 KB
• 最終ジャッジ日時: 2024-06-11 15:49:41
• 合計ジャッジ時間: 7,824 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 2 WA * 1
other	AC * 28 WA * 2

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.util.Arrays;
import java.util.Scanner;
public class Main86 {
    public static void main(String[] args) {
        Main86 p = new Main86();
    }
    char[][]  map;
    public Main86() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        map = new char[n][];
        for(int i=0;i<map.length;i++)
            map[i] = sc.next().toCharArray();
        solve(n, m);
    }
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    public void solve(int n, int m) {
        boolean res =false;
        int tc = 0;
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[i].length;j++){
                if(map[i][j]!='.')
                    continue;
                    
                int d = 0;
                for(int k=0;k<4;k++){
                    int nx = j+dx[k];
                    int ny = i+dy[k];
                    if(0<=nx && nx<map[0].length && 0<=ny && ny<map.length && map[ny][nx]=='.')
                        d += (k%2==0 ? 1 : 10);
                }
                
                if(d != 11 && d!=22)
                    continue;
                
                tc++;
                if(tc>10)
                    break;
                map[i][j] = 'a';
                for(int k=0;k<4;k++){
                    int nx = j+dx[k];
                    int ny = i+dy[k];
                    if(0<=nx && nx<map[0].length && 0<=ny && ny<map.length && map[ny][nx]=='.'){
//                      System.out.println(j +" " + i +" " + k);
                        map[i][j] = 'a';
                        res |= rec(nx, ny, k);
                        res = isOk();
                    }
                }
                
                map[i][j] = res ? 'a' : '.';
                if(res)
                    break;
            }
            
            if(tc>10 || res)
                break;
        }
        
        System.out.println(res ? "YES" : "NO");
    }
    private boolean isOk() {
        boolean ok = true;
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[i].length;j++){
                if(map[i][j]=='.')
                    ok = false;
                else if(map[i][j] == 'a')
                    map[i][j] = '.';
                
            }
        }
        return ok;
    }
    private boolean rec(int x, int y, int curDir) {
        
//      for(int i=0;i<map.length;i++)
//          System.out.println(Arrays.toString(map[i]));
//      System.out.println();
        
        for(int i=0;i<2;i++){
            int nx = x + dx[(curDir+i)%4];
            int ny = y + dy[(curDir+i)%4];
            
            if(nx<0 || map[0].length<=nx || ny<0 || map.length<=ny)
                continue;
            
            if(map[ny][nx]=='#')
                continue;
            
            map[y][x] = 'a';
            if(map[ny][nx]=='a')
                return true;
            
            boolean res = rec(nx, ny, (curDir+i)%4);
            if(res)
                return true;
            map[y][x] = '.';
        }
        
        return false;
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX