oj.uz

Submission #49655

# Submission time Handle Problem Language Result Execution time Memory
49655 2018-06-01T17:07:28 Z khsoo01 Robots (APIO13_robots) C++11
100 / 100
 1393 ms 59356 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

const int inf = 1e9, N = 505;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

int n, w, h, dt[9][9][N][N];
char ipt[N][N];

bool vis[N][N][4], solved[9][9];


pii ini[9], nxt[N][N][4];
queue<pii>q;

vector<pair<int,pii> > vec;

bool valid (int A, int B) {
	if(A < 1 || A > h) return false;
	if(B < 1 || B > w) return false;
	if(ipt[A][B] == 'x') return false;
	return true;
}

void calc(int A, int B, int i) {
	if(vis[A][B][i]) return;
	vis[A][B][i] = true;
	int nA = A+dx[i], nB = B+dy[i];
	if(!valid(nA,nB)) {
		nxt[A][B][i] = {A,B};
		return;
	}
	if(ipt[nA][nB]=='C') {
		calc(nA, nB, (i+1)%4);
		nxt[A][B][i] = nxt[nA][nB][(i+1)%4];
	}
	else if(ipt[nA][nB]=='A') {
		calc(nA, nB, (i+3)%4);
		nxt[A][B][i] = nxt[nA][nB][(i+3)%4];
	}
	else {
		calc(nA, nB, i);
		nxt[A][B][i] = nxt[nA][nB][i];
	}
}

void solve(int S, int E) {
	if(solved[S][E]) return;
	solved[S][E] = true;
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			dt[S][E][i][j] = inf;
		}
	}
	if(S == E) dt[S][E][ini[S].X][ini[S].Y] = 0;
	for(int k=S;k<E;k++) {
		solve(S,k);
		solve(k+1,E);
		for(int i=1;i<=h;i++) {
			for(int j=1;j<=w;j++) {
				dt[S][E][i][j] = min({inf, dt[S][E][i][j], dt[S][k][i][j] + dt[k+1][E][i][j]});
			}
		}
	}
	vec.clear();
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			vec.push_back({dt[S][E][i][j], {i, j}});
		}
	}
	sort(vec.begin(),vec.end());
	for(int k=0;k<vec.size();k++) {
		if(dt[S][E][vec[k].Y.X][vec[k].Y.Y] < vec[k].X) continue;
		q.push(vec[k].Y);
		while(!q.empty()) {
			int A, B;
			tie(A, B) = q.front();
			q.pop();
			for(int i=0;i<4;i++) {
				int nA, nB;
				tie(nA, nB) = nxt[A][B][i];
				if(dt[S][E][A][B] + 1 < dt[S][E][nA][nB]) {
					dt[S][E][nA][nB] = dt[S][E][A][B] + 1;
					q.push({nA, nB});
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&w,&h);
	for(int i=1;i<=h;i++) {
		scanf("%s",ipt[i]+1);
		for(int j=1;j<=w;j++) {
			if('1' <= ipt[i][j] && ipt[i][j] <= '9') {
				ini[ipt[i][j]-'1'] = {i, j};
			}
		}
	}
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			for(int k=0;k<4;k++) {
				calc(i,j,k);
			}
		}
	}
	solve(0,n-1);
	int ans = inf;
	for(int i=1;i<=h;i++) {
		for(int j=1;j<=w;j++) {
			ans = min(ans, dt[0][n-1][i][j]);
		}
	}
	printf("%d\n", ans == inf ? -1 : ans);
}

Compilation message

robots.cpp: In function 'void solve(int, int)':
robots.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int k=0;k<vec.size();k++) {
              ~^~~~~~~~~~~
robots.cpp: In function 'int main()':
robots.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&w,&h);
  ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",ipt[i]+1);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 568 KB Output is correct
5 Correct 3 ms 752 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 568 KB Output is correct
5 Correct 3 ms 752 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 3 ms 752 KB Output is correct
9 Correct 2 ms 752 KB Output is correct
10 Correct 2 ms 752 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 568 KB Output is correct
5 Correct 3 ms 752 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 3 ms 752 KB Output is correct
9 Correct 2 ms 752 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 420 ms 33400 KB Output is correct
12 Correct 18 ms 33400 KB Output is correct
13 Correct 303 ms 33400 KB Output is correct
14 Correct 478 ms 33748 KB Output is correct
15 Correct 478 ms 33932 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 568 KB Output is correct
5 Correct 3 ms 752 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 3 ms 752 KB Output is correct
9 Correct 2 ms 752 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 420 ms 33400 KB Output is correct
12 Correct 18 ms 33400 KB Output is correct
13 Correct 303 ms 33400 KB Output is correct
14 Correct 478 ms 33748 KB Output is correct
15 Correct 478 ms 33932 KB Output is correct
16 Correct 924 ms 58424 KB Output is correct
17 Correct 1391 ms 58720 KB Output is correct
18 Correct 925 ms 58780 KB Output is correct
19 Correct 1393 ms 59156 KB Output is correct
20 Correct 1211 ms 59356 KB Output is correct