#4825 (C++11) No.86 TVザッピング(2)

• 問題: No.86 TVザッピング(2)
• ユーザー: koyumeishi
• 提出日時: 2014-12-05 02:12:40
• 言語: C++11 (gcc 13.3.0)
• 結果: WA
• 実行時間: -
• コード長: 3,472 bytes
• コンパイル時間: 764 ms
• コンパイル使用メモリ: 82,732 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-11 15:42:22
• 合計ジャッジ時間: 1,748 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

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

ソースコード

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
//l b r u
int x[] = {-1,0,1,0};
int y[] = {0,1,0,-1};
int dfs(vector<vector<int> > &G, vector<bool> &visit, int pos){
    visit[pos] = true;
    int ret = 1;
    for(int i=0; i<G[pos].size(); i++){
        int next = G[pos][i];
        if(visit[next]) continue;
        ret += dfs(G, visit, next);
    }
    return ret;
}
int dfs_(vector<string> &G, int n, int m, vector<bool> &visit, int pos, int start, int toward, bool right){
    visit[pos] = true;
    int ret = 1;
    //進めるだけ進む
    //すでに訪れた点にぶつかるとそこで止まる。
    int xx = pos%m + x[toward];
    int yy = pos/m + y[toward];
    while(xx>=0 && xx < m && yy>=0 && yy < n){
        if(G[yy][xx]=='.' && !visit[xx+yy*m]){
            pos = xx + yy*m;
            visit[pos] = true;
            ret++;
            
            xx = pos%m + x[toward];
            yy = pos/m + y[toward];
        }else{
            break;
        }
    }
    //次がstart地点なら終了
    if(xx>=0 && xx < m && yy>=0 && yy < n && xx+yy*m == start){
        return ret;
    }
    //今いる場所から左に曲がる
    int next_x = pos%m + x[(toward+1)%4];
    int next_y = pos/m + y[(toward+1)%4];
    int next = next_x + next_y*m;
    //曲がった先の場所に進めるなら進む
    if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && !visit[next] && G[next_y][next_x]=='.' ){
        return ret + dfs_(G,n,m,visit, next, start, (toward+1)%4, right);
    }else{
        //次でstart地点に戻っていれば終了
        if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && next == start){
            return ret;
        }
    }
    //右に1回だけ曲がれる
    if(right==false){
        right = true;
        
        next_x = pos%m + x[(toward+3)%4];
        next_y = pos/m + y[(toward+3)%4];
        next = next_x + next_y*m;
        //曲がった先の場所に進めるなら進む
        if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && !visit[next] && G[next_y][next_x]=='.' ){
            return ret + dfs_(G,n,m,visit, next, start, (toward+3)%4, right);
        }else{
            //次でstart地点に戻っていれば終了
            if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && next == start){
                return ret;
            }
        }
    }
    
    //start地点に戻っていないのに行く先がなかったら不適切
    return -1;
    
}
int main(){
    int n,m;
    cin >> n >> m;
    vector<string> v(n);
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    vector<vector<int> > G(n*m);
    vector<int> s;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(v[i][j] == '.'){
                s.push_back(i*m + j);
                for(int k=0; k<4; k++){
                    int xx = j + x[k];
                    int yy = i + y[k];
                    if(xx<0 || xx >= m || yy<0 || yy >= n) continue;
                    if(v[yy][xx] == '.'){
                        G[m*i + j].push_back(yy*m + xx);
                    }
                }
            }
        }
    }
    vector<bool> visit(n*m, false);
    bool valid = dfs(G, visit, s[0]) == s.size();
    if(valid == false){
        cout << "NO" << endl;
        return 0;
    }
    valid = false;
    //最初に追加された点は必ず角になるので探索は1回で十分
    for(int i=0; i<1 && valid == false; i++){
        int start = s[i];
        int start_x = s[i]%m;
        int start_y = s[i]/m;
        for(int j=0; j<4 && valid == false; j++){
            fill(visit.begin(), visit.end(), false);
            int cnt = dfs_(v, n, m, visit, start, start, j, false);
            valid |= cnt == s.size();
        }
    }
    cout << (valid?"YES":"NO") << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX