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

• 問題: No.86 TVザッピング(2)
• ユーザー: koyumeishi
• 提出日時: 2014-12-05 02:25:20
• 言語: C++11 (gcc 13.3.0)
• 結果: AC
• 実行時間: 4 ms / 5,000 ms
• コード長: 3,481 bytes
• コンパイル時間: 1,075 ms
• コンパイル使用メモリ: 82,592 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-12-25 12:45:01
• 合計ジャッジ時間: 1,776 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 30

ソースコード

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
141
142
143
#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;
    int next_y;
    int next;
    //右に1回だけ曲がれる
    if(right==false){
        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, true);
        }else{
            //次でstart地点に戻っていれば終了
            if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && next == start){
                return ret;
            }
        }
    }
    
    //今いる場所から左に曲がる
    next_x = pos%m + x[(toward+1)%4];
    next_y = pos/m + y[(toward+1)%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+1)%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