제출 #375740

#제출 시각아이디문제언어결과실행 시간메모리
375740Ahmad_Hasan포탈들 (BOI14_portals)C++17
0 / 100
11 ms16256 KiB
#include <bits/stdc++.h> /** |||||||||| ||||| ||||| |||||||||| ||||||||||||| ||||| ||||| ||||| |||| |||||| ||||| ||||| ||||| ||||||||||||||||| ||||||||||||||| |||||||||| ||||||||||||||||||| ||||||||||||||| ||||| ||||| ||||| ||||| ||||| ||||| ||||| ||||| ||||| ||||| |||||||||| AHMED;HASSAN;SAEED; */ ///#define int long long using namespace std; int dirs[4][1005][1005]; vector<vector<int> >adj; int s,c; int n,m; int bfs(){ queue<int>q; vector<int>vis(n*m+5),d(n*m+5); q.push(s); int dis=0; while(!q.empty()){ int sz=q.size(); int f=0; while(sz--){ int cr=q.front(); q.pop(); if(vis[cr])continue; vis[cr]=1; d[cr]=dis; /**cout<<cr/n<<','<<cr%n<<'='<<d[cr]; cout<<'\n';*/ if(cr==c){ f=1; break; } for(int i=0;i<adj[cr].size();i++){ if(!vis[adj[cr][i]]){ q.push(adj[cr][i]); } } } if(f)break; dis++; } /** for(int i=0;i<n*m;i++){ cout<<i/n<<','<<i%n<<'='<<d[i]; cout<<'\n'; } */ return dis; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; adj.resize(n*m+5); vector<string>vs(n); for(int i=0;i<n;i++) cin>>vs[i]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(vs[i][j]=='S') s=i*n+j; if(vs[i][j]=='C') c=i*n+j; if(j+1<m&&vs[i][j]!='#'&&vs[i][j+1]!='#'){ adj[i*n+j].push_back(i*n+j+1); adj[i*n+j+1].push_back(i*n+j); } if(i+1<n&&vs[i][j]!='#'&&vs[i+1][j]!='#'){ adj[(i)*n+j].push_back((i+1)*n+j); adj[(i+1)*n+j].push_back(i*n+j); } } } memset(dirs,-1,sizeof(dirs)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(vs[i][j]=='#'){ dirs[0][i][j]=-1; dirs[1][i][j]=-1; }else{ if(j-1>=0&&dirs[0][i][j-1]!=-1){ dirs[0][i][j]=dirs[0][i][j-1]; }else{ dirs[0][i][j]=(i*n)+j; } if(i-1>=0&&dirs[1][i-1][j]!=-1){ dirs[1][i][j]=dirs[1][i-1][j]; }else{ dirs[1][i][j]=(i*n)+j; } } } } for(int i=n-1;i>=0;i--){ for(int j=m-1;j>=0;j--){ if(vs[i][j]=='#'){ dirs[2][i][j]=-1; dirs[3][i][j]=-1; }else{ if(j+1<m&&dirs[2][i][j+1]!=-1){ dirs[2][i][j]=dirs[2][i][j+1]; }else{ dirs[2][i][j]=(i*n)+j; } if(i+1<n&&dirs[3][i+1][j]!=-1){ dirs[3][i][j]=dirs[3][i+1][j]; }else{ dirs[3][i][j]=(i*n)+j; } } } } /** for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cout<<i*n+j<<' '; } cout<<'\n'; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cout<<dirs[0][i][j]<<' '; } cout<<'\n'; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cout<<dirs[1][i][j]<<' '; } cout<<'\n'; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cout<<dirs[1][i][j]<<' '; } cout<<'\n'; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cout<<dirs[3][i][j]<<' '; } cout<<'\n'; } */ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int f=0; for(int k=0;k<4;k++){ if(dirs[k][i][j]==i*n+j){ f=k+1; break; } } ///cout<<f<<' '; for(int k=0;k<4&&f;k++){ if(dirs[k][i][j]!=-1&&dirs[k][i][j]!=i*n+j){ adj[i*n+j].push_back(dirs[k][i][j]); ///adj[dirs[k][i][j]].push_back(i*n+j); } } } ///cout<<'\n'; } /** for(int i=0;i<n*m;i++){ cout<<i/n<<','<<i%n<<'='; for(int j=0;j<adj[i].size();j++) cout<<adj[i][j]<<' '; cout<<'\n'; } */ cout<<bfs()<<'\n'; return 0; } /** 1 8 2 abczzzzz */

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

portals.cpp: In function 'int bfs()':
portals.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int i=0;i<adj[cr].size();i++){
      |                         ~^~~~~~~~~~~~~~~
#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...