QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#119435 | #5580. Branch Manager | schwidola | TL | 0ms | 0kb | C++14 | 2.1kb | 2023-07-05 11:14:20 | 2023-07-05 11:14:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
enum Cell {
Wall = '#',
Normal = '.',
Immune = '@'
};
bool check_valid(int i, int j, int r, int c) {
return i >= 0 && j >= 0 && i < r && j < c;
}
bool check_upper_right(int i, int j, int r, int c) {
if (i == 0) {
return true;
}
return j == (c - 1);
}
int bfs(const vector <string>& v, int r, int c) {
vector <vector <int>> dist(r, vector <int>(c, -1));
const vector <int> dx{1, 1, 1, -1, -1, -1, 0, 0};
const vector <int> dy{0, 1, -1, 0, 1, -1, 1, -1};
deque <pair <int, int>> q;
for (int i = 0; i < r; i++) {
switch(v[i][0]) {
case Cell::Wall:
q.emplace_front(i, 0);
dist[i][0] = 0;
break;
case Cell::Normal:
q.emplace_back(i, 0);
dist[i][0] = 1;
break;
case Cell::Immune:
break;
default:
break;
}
}
for (int j = 0; j < c; j++) {
switch(v[r - 1][j]) {
case Cell::Wall:
q.emplace_front(r - 1, j);
dist[r - 1][j] = 0;
break;
case Cell::Normal:
q.emplace_back(r - 1, j);
dist[r - 1][j] = 1;
break;
case Cell::Immune:
break;
default:
break;
}
}
while (!q.empty()) {
auto [i, j] = q.front();
if (check_upper_right(i, j, r, c)) {
return dist[i][j];
}
q.pop_front();
for (int d = 0; d < 8; d++) {
int ni = i + dx[d];
int nj = j + dy[d];
if (!check_valid(ni, nj, r, c) || dist[ni][nj] != -1) {
continue;
}
switch(v[ni][nj]) {
case Cell::Wall:
dist[ni][nj] = dist[i][j];
q.emplace_front(ni, nj);
break;
case Cell::Normal:
dist[ni][nj] = dist[i][j] + 1;
q.emplace_back(ni, nj);
break;
case Cell::Immune:
break;
default:
break;
}
}
}
return -1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
while (1) {
int r, c;
cin >> r >> c;
if (r == 0 && c == 0) {
break;
}
vector <string> v(r);
for (int i = 0; i < r; i++) {
cin >> v[i];
}
cout << bfs(v, r, c) << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
8 5 1 2 4 8 4 6 1 4 2 5 4 7 2 3 5 2 6 4 8
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...