| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 155760 |
2019-09-30T09:27:41 Z |
brcode |
Portals (BOI14_portals) |
C++14 |
|
2 ms |
760 KB |
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
int n,m;
char grid[MAXN][MAXN];
pair<int,int> start;
bool portal[MAXN][MAXN];
vector<pair<int,int>> portals;
queue<pair<int,int>> q1;
priority_queue<pair<int,pair<int,int>>> pq;
pair<int,int> finish;
int dx[5] = {1,0,-1,0};
int dy[5] = {0,1,0,-1};
int portall[MAXN][MAXN];
int portald[MAXN][MAXN];
int portalr[MAXN][MAXN];
int portalu[MAXN][MAXN];
int dp[MAXN][MAXN];
int dpl[MAXN][MAXN];
int dpr[MAXN][MAXN];
int dpu[MAXN][MAXN];
int dpd[MAXN][MAXN];
int dist[MAXN][MAXN];
bool check(int x,int y){
if(x<=n && x>=1 && y<=m && y>=1){
return true;
}
return false;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>grid[i][j];
if(grid[i][j] == 'S'){
start = make_pair(i,j);
// cout<<i<<" "<<j<<endl;
}
if(grid[i][j] == 'C'){
finish = make_pair(i,j);
}
}
}
for(int i=1;i<=n;i++){
grid[i][0] = '#';
grid[i][m+1] = '#';
}
for(int i=1;i<=m;i++){
grid[0][i] = '#';
grid[n+1][i] = '#';
}
grid[0][0] = '#';
grid[0][m+1] = '#';
grid[n+1][0] = '#';
grid[n+1][m+1] = '#';
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
if(grid[i][j] == '#'){
for(int k=0;k<4;k++){
int x2 = i+dx[k];
int y2 = j+dy[k];
if(check(x2,y2) && grid[x2][y2]!='#'){
//if within grid and surrounding cell is a movable cell, place a portal here
//int dx[5] = {1,0,-1,0};
//int dy[5] = {0,1,0,-1};
if(k==0){
portalu[x2][y2] = true;
}
if(k==1){
portall[x2][y2] = true;
}
if(k==2){
portald[x2][y2] = true;
}
if(k==3){
portalr[x2][y2] = true;
}
portal[x2][y2] = true;
portals.push_back(make_pair(x2,y2));
}
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dist[i][j] = 1e9;
dp[i][j] = 1e9;
}
}
for(auto x:portals){
q1.push(x);
// cout<<x.first<<" "<<x.second<<endl;
dist[x.first][x.second] = 0;
}
while(!q1.empty()){
auto hold =q1.front();
q1.pop();
int x = hold.first;
int y = hold.second;
for(int i=0;i<4;i++){
int x2 = x+dx[i];
int y2 = y+dy[i];
if(check(x2,y2) && dist[x2][y2]==1e9 && grid[x2][y2]!='#'){
dist[x2][y2] = dist[x][y]+1;
q1.push(make_pair(x2,y2));
}
}
}
for(int i=1;i<=n;i++){
int hold = 1;
for(int j=1;j<=m;j++){
if(grid[i][j] == '#'){
continue;
}
if(!portalr[i][j] && !portall[i][j]){
dpl[i][j] = hold;
}else{
if(portalr[i][j]){
hold = j+1;
}else{
hold = j;
}
}
}
}
for(int i=1;i<=n;i++){
int hold = m;
for(int j=m;j>=1;j--){
if(grid[i][j] == '#'){
continue;
}
if(!portall[i][j] && !portalr[i][j]){
dpr[i][j] = hold;
}else{
if(portall[i][j]){
hold = j-1;
}else{
hold = j;
}
}
}
}
for(int i=1;i<=m;i++){
int hold = 1;
for(int j=1;j<=n;j++){
if(grid[j][i] == '#'){
continue;
}
if(!portald[j][i] && !portalu[j][i]){
dpu[j][i] = hold;
}else{
if(portald[j][i]){
hold = j+1;
}else{
hold = j;
}
}
}
}
for(int i=1;i<=m;i++){
int hold = n;
for(int j=n;j>=1;j--){
if(grid[j][i] == '#'){
continue;
}
if(!portalu[j][i] && !portald[j][i]){
dpd[j][i] = hold;
}else{
if(portalu[j][i]){
hold = j-1;
}else{
hold = j;
}
hold = j;
}
}
}
pq.push(make_pair(0,start));
dp[start.first][start.second] = 0;
while(!pq.empty()){
auto hold = pq.top();
pq.pop();
int w = hold.first;
int x = hold.second.first;
int y = hold.second.second;
if(x == finish.first && y == finish.second){
cout<<-1*w<<endl;
return 0;
}
for(int i=0;i<4;i++){
int x2 = x+dx[i];
int y2 = y+dy[i];
if(check(x2,y2) && grid[x2][y2]!='#' && dp[x2][y2]>dp[x][y]+1){
dp[x2][y2] = dp[x][y]+1;
pq.push(make_pair(-1*dp[x2][y2],make_pair(x2,y2)));
}
int p = dpl[x][y];
if(check(x,p) && grid[x][p] != '#' && dp[x][p]>dp[x][y]+dist[x][y]+1){
dp[x][p]=dp[x][y]+dist[x][y]+1;
pq.push(make_pair(-1*dp[x][p],make_pair(x,p)));
}
p = dpr[x][y];
if(check(x,p) && grid[x][p] != '#' && dp[x][p]>dp[x][y]+dist[x][y]+1){
dp[x][p]=dp[x][y]+dist[x][y]+1;
pq.push(make_pair(-1*dp[x][p],make_pair(x,p)));
}
p = dpu[x][y];
if(x == 4 && y == 3){
//cout<<123<<" "<<p<<endl;
//cout<<dp[p][y]<<" "<<dp[x][y]+dist[x][y]+1<<endl;
}
if(check(p,y) && grid[p][y] != '#' && dp[p][y]>dp[x][y]+dist[x][y]+1){
dp[p][y]=dp[x][y]+dist[x][y]+1;
pq.push(make_pair(-1*dp[p][y],make_pair(p,y)));
}
p = dpd[x][y];
if(check(p,y) && grid[p][y] != '#' && dp[p][y]>dp[x][y]+dist[x][y]+1){
dp[p][y]=dp[x][y]+dist[x][y]+1;
pq.push(make_pair(-1*dp[p][y],make_pair(p,y)));
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
2 ms |
632 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
