| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 197350 |
2020-01-20T13:32:08 Z |
dndhk |
Portals (BOI14_portals) |
C++14 |
|
24 ms |
24056 KB |
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int MOD = 1000000007; // 998244353
const int INF = 10000;
const ll INFLL = 1e18;
const int MAX_N = 1000;
int N, M;
string str[MAX_N+1];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int d1[MAX_N+1][MAX_N+1];
pii nxt[4][MAX_N+1][MAX_N+1];
int dist[MAX_N+1][MAX_N+1];
deque<pii> dq;
pii s, e;
vector<pair<pii, int> > gp[MAX_N+1][MAX_N+1];
bool vst[MAX_N+1][MAX_N+1];
priority_queue<pair<int, pii> , vector<pair<int, pii> > , greater<pair<int, pii> > > pq;
int main(){
scanf("%d%d", &N, &M);
for(int i=0; i<N; i++){
cin>>str[i];
for(int j=0; j<M; j++){
if(str[i][j]=='S'){
s = {i, j};
str[i][j] = '.';
}
if(str[i][j]=='C'){
e = {i, j};
str[i][j] = '.';
}
if(str[i][j]=='.'){
d1[i][j] = INF;
if(i==0 || i==N-1 || j==0 || j==M-1){
d1[i][j] = 0;
dq.pb({i, j});
}else{
for(int k=0; k<4; k++){
if(str[i+dx[k]][j+dy[k]]=='#'){
d1[i][j] = 0;
dq.pb({i, j});
break;
}
}
}
}
}
}
while(!dq.empty()){
pii now = dq.front(); dq.pop_front();
for(int i=0; i<4; i++){
if(now.first+dx[i]<0 || now.first+dx[i]>=N || now.second+dy[i]<0 || now.second+dy[i]>=M) continue;
if(str[now.first+dx[i]][now.second+dy[i]]=='#') continue;
if(d1[now.first+dx[i]][now.second+dy[i]]>d1[now.first][now.second]+1){
d1[now.first+dx[i]][now.second+dy[i]] = d1[now.first][now.second] + 1;
dq.pb({now.first+dx[i], now.second+dy[i]});
}
}
}
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(str[i][j]=='.'){
if(i==0 || str[i-1][j]=='#'){
int l = i, r = i;
while(r<N-1 && str[r+1][j]=='.'){
r++;
}
for(int k=l; k<=r; k++){
nxt[0][k][j] = {l, j};
nxt[1][k][j] = {r, j};
}
}
if(j==0 || str[i][j-1]=='#'){
int l = j, r = j;
while(r<M-1 && str[i][r+1]=='.'){
r++;
}
for(int k=l; k<=r; k++){
nxt[2][i][k] = {i, l};
nxt[3][i][k] = {i, r};
}
}
}
}
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(str[i][j]=='.'){
for(int k=0; k<4; k++){
gp[i][j].pb({nxt[k][i][j], d1[i][j] + 1});
if(i+dx[k]<0 || i+dx[k]>=N || j+dy[k]<0 || j+dy[k]>=M) continue;
if(str[i+dx[k]][j+dy[k]]=='#') continue;
gp[i][j].pb({{i+dx[k], j+dy[k]}, 1});
}
dist[i][j] = INF;
}
}
}
dist[s.first][s.second] = 0;
pq.push({0, s});
while(!pq.empty()){
pii p = pq.top().second; pq.pop();
if(vst[p.first][p.second]) continue;
vst[p.first][p.second] = true;
for(pair<pii, int> i : gp[p.first][p.second]){
if(dist[i.first.first][i.first.second]>dist[p.first][p.second] + i.second){
dist[i.first.first][i.first.second] = dist[p.first][p.second] + i.second;
pq.push({dist[i.first.first][i.first.second], i.first});
}
}
}
cout<<dist[e.first][e.second];
return 0;
}
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
24056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
