oj.uz

Submission #227696

# Submission time Handle Problem Language Result Execution time Memory
227696 2020-04-28T13:29:32 Z arman_ferdous Portals (BOI14_portals) C++17
0 / 100
 21 ms 28044 KB 
/* 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

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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28032 KB Output is correct
2 Correct 20 ms 28032 KB Output is correct
3 Correct 20 ms 28032 KB Output is correct
4 Correct 19 ms 27904 KB Output is correct
5 Incorrect 20 ms 28032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28032 KB Output is correct
2 Correct 19 ms 28032 KB Output is correct
3 Correct 19 ms 28016 KB Output is correct
4 Correct 19 ms 28032 KB Output is correct
5 Incorrect 19 ms 28032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28044 KB Output is correct
2 Correct 20 ms 28032 KB Output is correct
3 Correct 20 ms 28032 KB Output is correct
4 Incorrect 21 ms 28032 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28032 KB Output is correct
2 Correct 19 ms 28032 KB Output is correct
3 Correct 20 ms 28032 KB Output is correct
4 Correct 20 ms 28032 KB Output is correct
5 Incorrect 19 ms 28032 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28032 KB Output is correct
2 Correct 19 ms 28032 KB Output is correct
3 Correct 20 ms 28032 KB Output is correct
4 Correct 19 ms 28032 KB Output is correct
5 Incorrect 20 ms 28032 KB Output isn't correct
6 Halted 0 ms 0 KB -