제출 #141403

#제출 시각아이디문제언어결과실행 시간메모리
141403OrtPortal (COCI17_portal)C++11
36 / 120
74 ms12668 KiB
#include<bits/stdc++.h> #define MEM(a, b) memset(a, (b), sizeof(a)) #define ALL(c) (c).begin(),(c).end() #define LINF (int)1e18 #define INF (int)1e9 #define ll long long #define pb push_back #define mp make_pair #define MOD 1000000007 #define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define MAX 510 using namespace std; typedef pair<int,int> pii; int n, m, si, sj, ei, ej; string mat[MAX]; vector<pii> adm[MAX][MAX]; int v[MAX][MAX]; int dy[] = {1, -1, 0, 0}; int dx[] = {0, 0, 1, -1}; struct point{ int y, x, d; point(int y, int x, int d) { this->y = y; this->x = x; this->d = d; } }; queue<point> q; bool check(int y, int x) {return (y>=0 && y<n && x>=0 && x<m && mat[y][x]!='#');} inline void preprocess() { for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(mat[i][j]=='#') continue; if(mat[i][j-1]=='#') { for(int k=j;k<m;k++) { if(mat[i][k]=='#') break; if(i+1<n && mat[i+1][k]=='#') adm[i][k].pb(mp(i,j)); if(i-1>=0 && mat[i-1][k]=='#') adm[i][k].pb(mp(i,j)); } } if(mat[i][j+1]=='#') { for(int k=j;k>=0;k--) { if(mat[i][k]=='#') break; if(i+1<n && mat[i+1][k]=='#') adm[i][k].pb(mp(i,j)); if(i-1>=0 && mat[i-1][k]=='#') adm[i][k].pb(mp(i,j)); } } if(mat[i-1][j]=='#') { for(int k=i;k<n;k++) { if(mat[k][j]=='#') break; if(j+1<m && mat[k][j+1]=='#') adm[k][j].pb(mp(i,j)); if(j-1>=0 && mat[k][j-1]=='#') adm[k][j].pb(mp(i,j)); } } if(mat[i+1][j]=='#') { for(int k=i;k>=0;k--) { if(mat[k][j]=='#') break; if(j+1<m && mat[k][j+1]=='#') adm[k][j].pb(mp(i,j)); if(j-1>=0 && mat[k][j-1]=='#') adm[k][j].pb(mp(i,j)); } } } } int main() { IO; cin >> n >> m; for(int i=0;i<n;i++) cin >> mat[i]; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if(mat[i][j]=='C') { si = i; sj = j; } if(mat[i][j]=='F') { ei = i; ej = j; } } MEM(v, -1); preprocess(); q.push(point(si,sj,0)); while(!q.empty()) { point c = q.front(); q.pop(); if(c.y==ei && c.x==ej) { cout << c.d; return 0; } if(v[c.y][c.x]!=-1) continue; v[c.y][c.x] = c.d; for(auto u:adm[c.y][c.x]) q.push(point(u.first,u.second,c.d+1)); for(int k=0;k<4;k++) { int ny = c.y+dy[k]; int nx = c.x+dx[k]; if(check(ny,nx)) q.push(point(ny,nx,c.d+1)); } } cout << "nemoguce"; return 0; }
#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...
#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...