oj.uz

답안 #946590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946590 2024-03-14T19:13:20 Z vjudge1 포탈들 (BOI14_portals) C++11
11 / 100
 1000 ms 40408 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;

const int MAX = 1001;
const int INF = 1e6 + 1;

int r, c, sx, sy, ex, ey;
int ans = INF;
int maze[MAX][MAX];
map<vector<int>, bool> vis; 
int dx[5] = {1, 0, 0, -1, 0};
int dy[5] = {0, 1, -1, 0, 0};

bool good(int x, int y){
  return x >= 0 && x < r && y >= 0 && y < c && !maze[x][y];
}

class cmp {
public:
    bool operator() (vector<int> a, vector<int> b)
    {
        return a[2] > b[2];
    }
};

void trav(int x, int y){
  priority_queue<vector<int>, vector<vector<int>>, cmp> q;
  q.push({x, y, 0, -1, -1, -1, -1});
  vis[{x, y, 0, -1, -1, -1, -1}];
  while (!q.empty()){
    vector<int> t = q.top();
    q.pop();
    int a = t[0];
    int b = t[1];
    int s = t[2];
    if (a == ex && b == ey){
      cout << s << '\n';
      return;
    }
    vector<pair<int, int>> v = {{t[3], t[4]}, {t[5], t[6]}};
    for (int i = 0; i < 4; i++){
      int nx = a + dx[i];
      int ny = b + dy[i];
      while (good(nx, ny)){
        nx += dx[i]; ny += dy[i];
      }
      v.push_back({nx - dx[i], ny - dy[i]});
    }
    for (int i = 0; i < 5; i++){
      int nx = a + dx[i];
      int ny = b + dy[i];
      if (good(nx, ny)){
        for (int j = 0; j < v.size(); j++){
          for (int k = j + 1; k < v.size(); k++){
            if (v[j].first == v[k].first && v[j].second == v[k].second) continue;
            vector<int> l = {nx, ny, v[j].first, v[j].second, v[k].first, v[k].second};
            vector<int> o = {nx, ny, v[k].first, v[k].second, v[j].first, v[j].second};
            if (!vis[l] && !vis[o]){
              vis[l] = true;
              vis[o] = true;
              vector<int> temp = {l[0], l[1], s + abs(dx[i] + dy[i]), l[2], l[3], l[4], l[5]};
              q.push(temp);
            }
          }
        }
      }
    }
    if (a == t[3] && b == t[4]) { 
      vector<int> l = {t[5], t[6], t[3], t[4], t[5], t[6]};
      vector<int> o = {t[5], t[6], t[5], t[6], t[3], t[4]};
      if (!vis[l] && !vis[o]){
        vis[l] = true;
        vis[o] = true;
        vector<int> temp = {l[0], l[1], s + 1, l[2], l[3], l[4], l[5]};
        q.push(temp);
      }
    }
    if (a == t[5] && b == t[6]) { 
      vector<int> l = {t[3], t[4], t[3], t[4], t[5], t[6]};
      vector<int> o = {t[3], t[4], t[5], t[6], t[3], t[4]};
      if (!vis[l] && !vis[o]){
        vis[l] = true;
        vis[o] = true;
        vector<int> temp = {l[0], l[1], s + 1, l[2], l[3], l[4], l[5]};
        q.push(temp);
      }
    }
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> r >> c;
  char t;
  for (int i = 0; i < r; i++){
    for (int j = 0; j < c; j++){
      cin >> t;
      maze[i][j] = (t == '#' ? 1 : 0);
      if (t == 'S') {
        sx = i;
        sy = j;
      }
      if (t == 'C'){
        ex = i;
        ey = j;
      }
    }
  }
  trav(sx, sy);
  return 0;
}

Compilation message

portals.cpp: In function 'void trav(int, int)':
portals.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j = 0; j < v.size(); j++){
      |                         ~~^~~~~~~~~~
portals.cpp:58:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |           for (int k = j + 1; k < v.size(); k++){
      |                               ~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 33 ms 1736 KB Output is correct
4 Correct 14 ms 1116 KB Output is correct
5 Correct 172 ms 5716 KB Output is correct
6 Correct 29 ms 1876 KB Output is correct
7 Correct 329 ms 8044 KB Output is correct
8 Correct 22 ms 1620 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 10 ms 860 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 30 ms 1620 KB Output is correct
4 Correct 14 ms 948 KB Output is correct
5 Correct 184 ms 5784 KB Output is correct
6 Correct 30 ms 1880 KB Output is correct
7 Correct 313 ms 8068 KB Output is correct
8 Correct 22 ms 1616 KB Output is correct
9 Execution timed out 1078 ms 38264 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 30 ms 1572 KB Output is correct
4 Correct 172 ms 5716 KB Output is correct
5 Execution timed out 1053 ms 26116 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 32 ms 1620 KB Output is correct
4 Correct 14 ms 1112 KB Output is correct
5 Correct 173 ms 5712 KB Output is correct
6 Correct 29 ms 1872 KB Output is correct
7 Correct 328 ms 8480 KB Output is correct
8 Correct 22 ms 1628 KB Output is correct
9 Execution timed out 1050 ms 40408 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 31 ms 1620 KB Output is correct
4 Correct 14 ms 1116 KB Output is correct
5 Correct 185 ms 5824 KB Output is correct
6 Correct 29 ms 1884 KB Output is correct
7 Correct 346 ms 8032 KB Output is correct
8 Correct 22 ms 1628 KB Output is correct
9 Execution timed out 1068 ms 39684 KB Time limit exceeded
10 Halted 0 ms 0 KB -