Submission #227696

#	Time	Username	Problem	Language	Result	Execution time	Memory
227696		arman_ferdous	Portals (BOI14_portals)	C++17	0 / 100	21 ms	28044 KiB

portals

/* Author : arman_ferdous 
 * Date   : 28 Apr 2020 18:52:39
 * TAG    : Noob Problem 
 */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int,int>;

const int N = 1005;
int n, m;
char s[N][N];
vector<pair<int,int>> g[N][N];

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
int dist[N][N];
queue<pair<int,int>> q;
int main() { 
  scanf("%d %d", &n, &m);
  for(int j = 0; j <= m + 1; j++)
    s[0][j] = s[n + 1][j] = '#';
  for(int i = 1; i <= n; i++) {
    scanf(" %s", s[i] + 1);
    s[i][0] = '#';
    s[i][m + 1] = '#';
  }
  for(int i = 1; i <= n; i++) {
    int last = 0;
    for(int j = 1; j <= m + 1; j++) {
      if(s[i][j] == '#') {
        if(last + 2 < j - 1) {
          g[i][last + 1].push_back({i, j - 1});
          g[i][j - 1].push_back({i, last + 1});
        }
        last = j;
      }
    }
  }
  for(int j = 1; j <= m; j++) {
    int last = 0;
    for(int i = 1; i <= n + 1; i++) {
      if(s[i][j] == '#') {
        if(last + 2 < i - 1) {
          g[last + 1][j].push_back({i - 1, j});
          g[i - 1][j].push_back({last + 1, j});
        }
        last = i;
      }
    }
  }
  int sx, sy;
  int cx, cy;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      if(s[i][j] == 'S') sx = i, sy = j;
      else if(s[i][j] == 'C') cx = i, cy = j;
    }
  }
  memset(dist, -1, sizeof dist);
  dist[sx][sy] = 0;
  q.push({sx, sy});
  while(!q.empty()) {
    int x = q.front().first, y = q.front().second;
    q.pop();
    for(int k = 0; k < 4; k++) {
      int tx = x + dx[k], ty = y + dy[k];
      if(s[tx][ty] == '#' || dist[tx][ty] != -1) continue;
      dist[tx][ty] = dist[x][y] + 1;
      q.push({tx, ty});
    }
    for(auto t : g[x][y]) {
      int tx = t.first, ty = t.second;
      if(s[tx][ty] == '#' || dist[tx][ty] != -1) continue;
      dist[tx][ty] = dist[x][y] + 1;
      q.push({tx, ty});
    }
  }
  printf("%d\n", dist[cx][cy]);
  return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
portals.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", s[i] + 1);
     ~~~~~^~~~~~~~~~~~~~~~~
portals.cpp:81:9: warning: 'cy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   printf("%d\n", dist[cx][cy]);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
portals.cpp:81:9: warning: 'cx' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30