제출 #30901

#제출 시각아이디문제언어결과실행 시간메모리
30901Navick포탈들 (BOI14_portals)C++14
20 / 100
23 ms52552 KiB
#include <bits/stdc++.h> #define F first #define S second #define pii pair<int, int> #define pb push_back #define end ENND using namespace std; typedef long long ll; typedef long double ld; const int N = 1010, INF = 1e9; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; //down,right,up,left. int d[N][N], dis[N][N]; pii start, end, que[N * N], nex[4][N][N]; bool mp[N][N]; char sr[N]; set<pair<int, pii> > s; int main(){ int n, m; scanf("%d %d",&n ,&m); for(int i=1; i<=n; i++){ scanf("%s", sr); for(int j=1; j<=m; j++){ if(sr[j - 1] == '.'){ mp[i][j] = true; d[i][j] = INF; } else if(sr[j - 1] == 'S'){ mp[i][j] = true; d[i][j] = INF; start = {i, j}; }else if(sr[j - 1] == 'C'){ mp[i][j] = true; d[i][j] = INF; end = {i, j}; } } } int st = 0, en = 0; for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) if(!mp[i][j]) que[en++] = {i, j}; while(en - st){ pii v = que[st++]; int x = v.F, y = v.S; for(int i=0; i<4; i++){ int nx = x + dx[i], ny = y + dy[i]; if(nx < 0 || nx > n + 1 || ny < 0 || ny > m + 1)continue; if(d[nx][ny] == INF){ d[nx][ny] = d[x][y] + 1; que[en++] = {nx, ny}; } } } for(int i=n+1; i>=0; i--) for(int j=m+1; j>=0; j--){ if(!mp[i][j])continue; for(int c=0; c<2; c++){ int nx = i + dx[c], ny = j + dy[c]; if(nx < 0 || nx > n + 1 || ny < 0 || ny > m + 1)continue; if(mp[nx][ny]) nex[c][i][j] = nex[c][nx][ny]; else nex[c][i][j] = {i, j}; } } for(int i=0; i<=n+1; i++){ for(int j=0; j<=m+1; j++){ if(!mp[i][j])continue; for(int c=2; c<4; c++){ int nx = i + dx[c], ny = j + dy[c]; if(nx < 0 || ny > n + 1 || ny < 0 || ny > m + 1)continue; if(mp[nx][ny]) nex[c][i][j] = nex[c][nx][ny]; else nex[c][i][j] = {i, j}; } } } //dijkstra :) for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++){ if(!mp[i][j])continue; dis[i][j] = INF; if(i != start.F || j != start.S) s.insert({dis[i][j], {i, j}}); } dis[start.F][start.S] = 0; s.insert({0, start}); while(!s.empty()){ auto X = *(s.begin()); s.erase(s.begin()); int res = X.F; int x = X.S.F, y = X.S.S; for(int i=0; i<4; i++){ int nx = x + dx[i], ny = y + dy[i]; if(nx < 0 || nx > n + 1 || ny < 0 || ny > m + 1)continue; if(!mp[nx][ny])continue; if(dis[nx][ny] > res + 1){ s.erase({dis[nx][ny], {nx, ny}}); dis[nx][ny] = res + 1; s.insert({dis[nx][ny], {nx, ny}}); } } for(int i=0; i<4; i++){ int nx = nex[i][x][y].F, ny = nex[i][x][y].S; if(dis[nx][ny] > res + d[x][y]){ s.erase({dis[nx][ny], {nx, ny}}); dis[nx][ny] = res + d[x][y]; s.insert({dis[nx][ny], {nx, ny}}); } } } /* for(int c=0; c<4; c++){ cout << c << endl; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++) if(mp[i][j])cout << nex[c][i][j].F << ',' << nex[c][i][j].S << ' '; else cout << -1 << ',' << -1 << ' '; cout << endl; } cout << endl; } for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++) cout << d[i][j] << ' '; cout << endl; } */ printf("%d\n", dis[end.F][end.S]); }

컴파일 시 표준 에러 (stderr) 메시지

portals.cpp: In function 'int main()':
portals.cpp:27:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d %d",&n ,&m);
                                 ^
portals.cpp:29:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", sr);
                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...