제출 #742958

#제출 시각아이디문제언어결과실행 시간메모리
742958Dan4Life포탈들 (BOI14_portals)C++17
20 / 100
10 ms14220 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define sz(a) (int)a.size() const int mxN = (int)1e3+10; int X[] = {1,-1,0,0}; int Y[] = {0,0,1,-1}; int n, m, stX, stY, enX, enY; string a[mxN]; queue<pair<int,int>> Q; int dis[mxN][mxN]; pair<int,int> dir[4][mxN][mxN]; bool valid(int i, int j){ return i>=0 and j>=0 and i<n and j<m and a[i][j]!='#'; } void bfs(int i, int j){ memset(dis,-1,sizeof(dis)); Q.push({i,j}); dis[i][j] = 0; while(!Q.empty()){ auto [i,j] = Q.front(); bool ok = 0; Q.pop(); for(int k = 0; k < 4; k++){ int ni = i+X[k], nj = j+Y[k]; if(valid(ni,nj) and dis[ni][nj]==-1) dis[ni][nj] = dis[i][j]+1, Q.push({ni,nj}); else if(!valid(ni,nj)) ok=1; } for(int k = 0; k < 4 and ok; k++){ auto [ni,nj] = dir[k][i][j]; if(valid(ni,nj) and dis[ni][nj]==-1) dis[ni][nj] = dis[i][j]+1, Q.push({ni,nj}); } } } int32_t main(){ cin >> n >> m; for(int i = 0; i < n; i++){ cin >> a[i]; for(int j = 0; j < m; j++){ if(a[i][j]=='C') enX=i,enY=j; else if(a[i][j]=='S') stX=i,stY=j; } } for(int i = 0; i < n; i++){ int last = 0; for(int j = 0; j < m; j++){ if(a[i][j]=='#') last = j+1; else dir[0][i][j]={i,last}; } last = m-1; for(int j = m-1; j >= 0; j--){ if(a[i][j]=='#') last = j-1; else dir[1][i][j]={i,last}; } } for(int j = 0; j < m; j++){ int last = 0; for(int i = 0; i < n; i++){ if(a[i][j]=='#') last = i+1; else dir[2][i][j]={last,j}; } last = n-1; for(int i = n-1; i >= 0; i--){ if(a[i][j]=='#') last = i-1; else dir[3][i][j]={last,j}; } } bfs(stX,stY); cout << dis[enX][enY]; }
#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...