oj.uz

Submission #141405

# Submission time Handle Problem Language Result Execution time Memory
141405 2019-08-07T23:09:51 Z Ort Portal (COCI17_portal) C++11
96 / 120
 89 ms 14312 KB 
#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;
					else if(i+1<n && mat[i+1][k]=='#') adm[i][k].pb(mp(i,j));
					else if(i-1>=0 && mat[i-1][k]=='#') adm[i][k].pb(mp(i,j));
					if(k+1<m && mat[i][k+1]=='#') adm[i][k].pb(mp(i,j)), adm[i][j].pb(mp(i,k));
				}
			}
			if(mat[i][j+1]=='#') {
				for(int k=j;k>=0;k--) {
					if(mat[i][k]=='#') break;
					else if(i+1<n && mat[i+1][k]=='#') adm[i][k].pb(mp(i,j));
					else 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;
					else if(j+1<m && mat[k][j+1]=='#') adm[k][j].pb(mp(i,j));
					else if(j-1>=0 && mat[k][j-1]=='#') adm[k][j].pb(mp(i,j));
					if(k+1<n && mat[k+1][j]=='#') adm[k][j].pb(mp(i,j)), adm[i][j].pb(mp(k,j));
				}
			}
			if(mat[i+1][j]=='#') {
				for(int k=i;k>=0;k--) {
					if(mat[k][j]=='#') break;
					else if(j+1<m && mat[k][j+1]=='#') adm[k][j].pb(mp(i,j));
					else 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;
			}
		}
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) v[i][j] = INF;
	preprocess();
	q.push(point(si,sj,0));
	while(!q.empty()) {
		point c = q.front();
		q.pop();
		if(v[c.y][c.x]<=c.d) 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));
		}
	}
	if(v[ei][ej]==INF) cout << "nemoguce";
	else cout << v[ei][ej];
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6520 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6520 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6520 KB Output is correct
2 Correct 7 ms 6520 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6520 KB Output is correct
2 Correct 7 ms 6520 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6520 KB Output is correct
2 Correct 7 ms 6524 KB Output is correct
3 Correct 7 ms 6520 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7480 KB Output is correct
2 Correct 11 ms 7288 KB Output is correct
3 Correct 13 ms 7288 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 8684 KB Output is correct
2 Correct 12 ms 7928 KB Output is correct
3 Correct 15 ms 7672 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11384 KB Output is correct
2 Correct 45 ms 10744 KB Output is correct
3 Correct 27 ms 9592 KB Output is correct

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 13876 KB Output is correct
2 Correct 49 ms 14188 KB Output is correct
3 Correct 45 ms 11184 KB Output is correct
4 Incorrect 36 ms 10572 KB Output isn't correct

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 14312 KB Output isn't correct
2 Halted 0 ms 0 KB -