QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#119435#5580. Branch ManagerschwidolaTL 0ms0kbC++142.1kb2023-07-05 11:14:202023-07-05 11:14:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-05 11:14:26]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-07-05 11:14:20]
  • 提交

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
...

result: