Submission #00213

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
int main() {
int h, w;
cin >> h >> w;
string a[h];
pair<int, int> s, g;
for (int i = 0; i < h; i++) {
cin >> a[i];
int pos = a[i].find("S");
if (pos != -1) {
s = {i, pos};
a[i][pos] = '.';
}
pos = a[i].find("G");
if (pos != -1) {
g = {i, pos};
a[i][pos] = '.';
}
}
queue<pair<int, int>> q;
q.push(s);
vector<vector<vector<int>>> dist(2, vector<vector<int>>(h, vector<int>(w, -1)));
dist[0][s.first][s.second] = 0;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
if (y - 1 >= 0 && a[y - 1][x] != '#') {
if (a[y][x] == 'D' || a[y][x] == 'L' || a[y][x] == 'R') {
if (dist[1][y - 1][x] == -1) {
dist[1][y - 1][x] = dist[0][y][x] + 1;
q.push({y - 1, x});
}
} else {
bool check = false;
if (dist[0][y][x] != -1 && dist[0][y - 1][x] == -1) {
dist[0][y - 1][x] = dist[0][y][x] + 1;
check = true;
}
if (dist[1][y][x] != -1 && dist[1][y - 1][x] == -1) {
dist[1][y - 1][x] = dist[1][y][x] + 1;
check = true;
}
if (check) {
q.push({y - 1, x});
}
}
}
if (y + 1 < h && a[y + 1][x] != '#') {
if (a[y][x] == 'U' || a[y][x] == 'L' || a[y][x] == 'R') {
if (dist[1][y + 1][x] == -1) {
dist[1][y + 1][x] = dist[0][y][x] + 1;
q.push({y + 1, x});
}
} else {
bool check = false;
if (dist[0][y][x] != -1 && dist[0][y + 1][x] == -1) {
dist[0][y + 1][x] = dist[0][y][x] + 1;
check = true;
}
if (dist[1][y][x] != -1 && dist[1][y + 1][x] == -1) {
dist[1][y + 1][x] = dist[1][y][x] + 1;
check = true;
}
if (check) {
q.push({y + 1, x});
}
}
}
if (x - 1 >= 0 && a[y][x - 1] != '#') {
if (a[y][x] == 'U' || a[y][x] == 'D' || a[y][x] == 'R') {
if (dist[1][y][x - 1] == -1) {
dist[1][y][x - 1] = dist[0][y][x] + 1;
q.push({y, x - 1});
}
} else {
bool check = false;
if (dist[0][y][x] != -1 && dist[0][y][x - 1] == -1) {
dist[0][y][x - 1] = dist[0][y][x] + 1;
check = true;
}
if (dist[1][y][x] != -1 && dist[1][y][x - 1] == -1) {
dist[1][y][x - 1] = dist[1][y][x] + 1;
check = true;
}
if (check) {
q.push({y, x - 1});
}
}
}
if (x + 1 < w && a[y][x + 1] != '#') {
if (a[y][x] == 'U' || a[y][x] == 'D' || a[y][x] == 'L') {
if (dist[1][y][x + 1] == -1) {
dist[1][y][x + 1] = dist[0][y][x] + 1;
q.push({y, x + 1});
}
} else {
bool check = false;
if (dist[0][y][x] != -1 && dist[0][y][x + 1] == -1) {
dist[0][y][x + 1] = dist[0][y][x] + 1;
check = true;
}
if (dist[1][y][x] != -1 && dist[1][y][x + 1] == -1) {
dist[1][y][x + 1] = dist[1][y][x] + 1;
check = true;
}
if (check) {
q.push({y, x + 1});
}
}
}
}
/* for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cout << dist[0][i][j] << " ";
}
cout << "\n";
}
cout << "\n";
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cout << dist[1][i][j] << " ";
}
cout << "\n";
}
cout << "\n"; */
if (dist[0][g.first][g.second] == -1 && dist[1][g.first][g.second] == -1) {
cout << -1 << "\n";
} else if (dist[0][g.first][g.second] == -1) {
cout << dist[1][g.first][g.second] << "\n";
} else if (dist[1][g.first][g.second] == -1) {
cout << dist[0][g.first][g.second] << "\n";
} else {
cout << min(dist[0][g.first][g.second], dist[1][g.first][g.second]) << "\n";
}
return(0);
}

ステータス

項目 データ
問題 0008 - 一方通行迷路ゲーム
ユーザー名 woody_1227
投稿日時 2023-08-28 11:51:41
言語 C++17
状態 Wrong Answer
得点 0
ソースコード長 4886 Byte
最大実行時間 33 ms
最大メモリ使用量 1984 KB

セット

セット 得点 Cases
1 ALL 0 / 30 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 18 ms 476 KB
1
in2 WA 19 ms 608 KB
1
in3 WA 21 ms 520 KB
1
in4 AC 25 ms 616 KB
1
in5 AC 20 ms 584 KB
1
in6 AC 20 ms 676 KB
1
in7 AC 18 ms 644 KB
1
in8 WA 22 ms 744 KB
1
in9 WA 33 ms 1112 KB
1
in10 WA 21 ms 824 KB
1
in11 WA 19 ms 656 KB
1
in12 WA 28 ms 608 KB
1
in13 WA 25 ms 712 KB
1
in14 AC 23 ms 1736 KB
1
in15 WA 24 ms 1868 KB
1
in16 WA 28 ms 1872 KB
1
in17 WA 23 ms 1876 KB
1
in18 WA 24 ms 1880 KB
1
in19 WA 30 ms 1884 KB
1
in20 WA 26 ms 1984 KB
1
in21 WA 26 ms 1868 KB
1
in22 AC 28 ms 1876 KB
1
in23 WA 30 ms 1888 KB
1
in24 AC 21 ms 1896 KB
1
in25 WA 24 ms 1904 KB
1
in26 WA 27 ms 1908 KB
1
in27 WA 22 ms 1916 KB
1
in28 WA 33 ms 1792 KB
1