Submission #946590

#	Time	Username	Problem	Language	Result	Execution time	Memory
946590		vjudge1	Portals (BOI14_portals)	C++11	11 / 100	1078 ms	40408 KiB

portals

#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 (stderr)

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 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30