#include <bits/stdc++.h>
// #define int long long
using namespace std;
const int N=1005;
char grid[N][N];
int dis[N][N];
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0};int x,y;
vector<pair<int,pair<int,int>>>adj[N][N];vector<pair<int,pair<int,int>>>se[N][N];
void dijsktra(int r,int c){
int vis[x+1][y+1];
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
vis[i][j]=0;dis[i][j]=INT_MAX;
}
}
set<pair<int,pair<int,int>>>ve;
ve.insert({0,{r,c}});
dis[r][c]=0;
while(!ve.empty()){
pair<int,pair<int,int>>q=*(ve.begin());
ve.erase(*(ve.begin()));
if(vis[q.second.first][q.second.second]){
continue;
}
vis[q.second.first][q.second.second]=1;
for(auto i:se[q.second.first][q.second.second]){
for(auto j:se[q.second.first][q.second.second]){
if(i==j){
continue;
}
if(dis[i.second.first][i.second.second]>j.first+q.first+1){
dis[i.second.first][i.second.second]=j.first+q.first+1;
ve.insert({dis[i.second.first][i.second.second],{i.second.first,i.second.second}});
}
if(dis[j.second.first][j.second.second]>i.first+q.first+1){
dis[j.second.first][j.second.second]=i.first+q.first+1;
ve.insert({dis[j.second.first][j.second.second],{j.second.first,j.second.second}});
}
}
}
for(auto u:adj[q.second.first][q.second.second]){
if(dis[u.second.first][u.second.second]>q.first+u.first){
dis[u.second.first][u.second.second]=q.first+u.first;
ve.insert({dis[u.second.first][u.second.second],{u.second.first,u.second.second}});
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
cin>>x;cin>>y;int stx;int sty;int enx;int eny;
memset(grid,'#',sizeof(grid));
for(int i=1;i<=x;i++){
for(int j=1;j<=y;j++){
cin>>grid[i][j];
if(grid[i][j]=='S'){
stx=i;sty=j;
}
if(grid[i][j]=='C'){
enx=i;eny=j;
}
}
}
for(int i=0;i<=x+1;i++){
for(int j=0;j<=y+1;j++){
if(grid[i][j]!='#'){
for(int r=0;r<4;r++){
int newx=nx[r]+i;int newy=ny[r]+j;
if(newx>=1&&newx<=x&&newy>=1&&newy<=y&&grid[newx][newy]!='#'){
adj[i][j].push_back({1,{newx,newy}});
}
}
}
if(grid[i][j]=='#'){
int l=i-1;
if(i!=0){
//up
while(l!=0){
if(grid[l-1][j]=='#'){
break;
}
l--;
}
if(l!=i-1&&i!=0){
adj[i-1][j].push_back({1,{l,j}});
}
}
l=i+1;
while(l!=x+1){
if(grid[l+1][j]=='#'){
break;
}
l++;
}
if(l!=i+1){
adj[i+1][j].push_back({1,{l,j}});
}
//right
l=j+1;
while(l!=y+1){
if(grid[i][l+1]=='#'){
break;
}
l++;
}
if(l!=j+1){
adj[i][j+1].push_back({1,{i,l}});
}
//left
l=j-1;
while(l!=0){
if(grid[i][l-1]=='#'){
break;
}
l--;
}
if(l!=j-1&&j!=0){
adj[i][j-1].push_back({1,{i,l}});
}
}
if(grid[i][j]!='#'){
//up
int l=i-1;
if(grid[l][j]!='#'){
if(l!=0){
while(true){
if(grid[l-1][j]=='#'){
break;
}
l--;
}
}
se[i][j].push_back({abs(l-i),{l,j}});
}
//down
l=i+1;
if(grid[l][j]!='#'){
while(true){
if(grid[l+1][j]=='#'){
break;
}
l++;
}
se[i][j].push_back({abs(l-i),{l,j}});
}
//right;
l=j+1;
if(grid[i][l]!='#'){
while(true){
if(grid[i][l+1]=='#'){
break;
}
l++;
}
se[i][j].push_back({abs(j-l),{i,l}});
}
//left
if(grid[i][l]!='#'){
l=j-1;
if(l!=0){
while(true){
if(grid[i][l-1]=='#'){
break;
}
l--;
}
}
se[i][j].push_back({abs(j-l),{i,l}});
}
}
}
}
dijsktra(stx,sty);
cout<<dis[enx][eny]<<endl;
}
Compilation message
portals.cpp: In function 'int main()':
portals.cpp:183:31: warning: 'eny' may be used uninitialized in this function [-Wmaybe-uninitialized]
183 | cout<<dis[enx][eny]<<endl;
| ^
portals.cpp:183:31: warning: 'enx' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:182:21: warning: 'sty' may be used uninitialized in this function [-Wmaybe-uninitialized]
182 | dijsktra(stx,sty);
| ~~~~~~~~^~~~~~~~~
portals.cpp:182:21: warning: 'stx' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
48732 KB |
Output is correct |
| 2 |
Correct |
61 ms |
48744 KB |
Output is correct |
| 3 |
Correct |
59 ms |
48740 KB |
Output is correct |
| 4 |
Correct |
60 ms |
48740 KB |
Output is correct |
| 5 |
Incorrect |
59 ms |
48724 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
48664 KB |
Output is correct |
| 2 |
Correct |
73 ms |
48748 KB |
Output is correct |
| 3 |
Correct |
66 ms |
48736 KB |
Output is correct |
| 4 |
Correct |
61 ms |
48740 KB |
Output is correct |
| 5 |
Incorrect |
63 ms |
48732 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
48696 KB |
Output is correct |
| 2 |
Correct |
59 ms |
48744 KB |
Output is correct |
| 3 |
Correct |
61 ms |
48732 KB |
Output is correct |
| 4 |
Incorrect |
60 ms |
48748 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
48736 KB |
Output is correct |
| 2 |
Correct |
65 ms |
48736 KB |
Output is correct |
| 3 |
Correct |
59 ms |
48752 KB |
Output is correct |
| 4 |
Correct |
60 ms |
48736 KB |
Output is correct |
| 5 |
Incorrect |
66 ms |
48736 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
48740 KB |
Output is correct |
| 2 |
Correct |
60 ms |
48748 KB |
Output is correct |
| 3 |
Correct |
60 ms |
48760 KB |
Output is correct |
| 4 |
Correct |
60 ms |
48748 KB |
Output is correct |
| 5 |
Incorrect |
60 ms |
48736 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
