oj.uz

Submission #162096

# Submission time Handle Problem Language Result Execution time Memory
162096 2019-11-06T11:13:59 Z HungAnhGoldIBO2020 Robots (APIO13_robots) C++14
100 / 100
 511 ms 125032 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=501;
const int TOTAL=N*N;
const int M=10;
const int inf=1e9+7;
const int LIM=TOTAL*10;
int n,m,dis[M][M][TOTAL],go[5][TOTAL],dx[]={0,-1,0,1},dy[]={-1,0,1,0},nm;
char dime[N][N];
bool valid(int x,int y){
	if(x>=1&&x<=n){
		if(y>=1&&y<=m){
			if(dime[x][y]!='x'){
				return true;
			}
		}
	}
	return false;
}
int idx(int x,int y){
	return (x-1)*m+y;
}
bool cac=true;
int dfs(int dir,int x,int y){
	if(!valid(x,y)){
		return idx(x-dx[dir],y-dy[dir]);
	}
	if(go[dir][idx(x,y)]!=0){
		return go[dir][idx(x,y)];
	}
	go[dir][idx(x,y)]=-1;
	if(dime[x][y]=='C'){
		go[dir][idx(x,y)]=dfs((dir+1)%4,x+dx[(dir+1)%4],y+dy[(dir+1)%4]);
	}
	else{
		if(dime[x][y]=='A'){
			go[dir][idx(x,y)]=dfs((dir+3)%4,x+dx[(dir+3)%4],y+dy[(dir+3)%4]);
		}
		else{
			go[dir][idx(x,y)]=dfs(dir,x+dx[dir],y+dy[dir]);
		}
	}
	return go[dir][idx(x,y)];
}
void bfs(int val,int pos){
	queue<int> q;
	q.push(pos);
	while(q.size()){
		pos=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			if(go[i][pos]!=-1){
				if(dis[val][val][go[i][pos]]>dis[val][val][pos]+1){
					dis[val][val][go[i][pos]]=dis[val][val][pos]+1;
					q.push(go[i][pos]);
				}
			}
		}
	}
}
vector<int> lis[LIM];
void dijkstra(int l,int r){
	int i,j,k,cnt=0;
	for(i=1;i<=nm;i++){
		if(dis[l][r][i]<LIM){
			lis[dis[l][r][i]].push_back(i);
			cnt++;
		}
	}
	for(i=0;i<LIM&&cnt;i++){
		while(lis[i].size()){
			j=lis[i].back();
			lis[i].pop_back();
			cnt--;
			if(dis[l][r][j]!=i||i==LIM-1){
				continue;
			}
			for(k=0;k<4;k++){
				if(go[k][j]!=-1){
					if(dis[l][r][go[k][j]]>dis[l][r][j]+1){
						dis[l][r][go[k][j]]=dis[l][r][j]+1;
						lis[i+1].push_back(go[k][j]);
						cnt++;
					}
				}
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int i,j,k,l,num,z;
	cin>>num>>m>>n;
	nm=n*m;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin>>dime[i][j];
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(dime[i][j]=='x'){
				continue;
			}
			for(k=0;k<4;k++){
				if(!go[k][idx(i,j)]){
					dfs(k,i,j);
				}
			}
		}
	}
	//cout<<go[1][47]<<endl;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(dime[i][j]>='1'&&dime[i][j]<='9'){
				for(k=1;k<=nm;k++){
					dis[(int)(dime[i][j]-'1')][(int)(dime[i][j]-'1')][k]=inf;
				}
				dis[(int)(dime[i][j]-'1')][(int)(dime[i][j]-'1')][idx(i,j)]=0;
				bfs((int)(dime[i][j]-'1'),idx(i,j));
			}
		}
	}
	for(l=1;l<num;l++){
		for(i=0;i+l<num;i++){
			j=i+l;
			for(z=1;z<=nm;z++){
				dis[i][j][z]=inf;
			}
			for(k=i;k<j;k++){		//(i,k) and (k+1,j)
				for(z=1;z<=nm;z++){
					dis[i][j][z]=min(dis[i][j][z],dis[i][k][z]+dis[k+1][j][z]);
				}
			}
			dijkstra(i,j);
		}
	}
	int ans=inf;
	for(i=1;i<=nm;i++){
		ans=min(ans,dis[0][num-1][i]);
	}
	if(ans==inf){
		cout<<-1;
	}
	else{
		cout<<ans;
	}
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 59256 KB Output is correct
2 Correct 59 ms 59256 KB Output is correct
3 Correct 57 ms 59512 KB Output is correct
4 Correct 58 ms 59256 KB Output is correct
5 Correct 58 ms 59312 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 59256 KB Output is correct
2 Correct 59 ms 59256 KB Output is correct
3 Correct 57 ms 59512 KB Output is correct
4 Correct 58 ms 59256 KB Output is correct
5 Correct 58 ms 59312 KB Output is correct
6 Correct 58 ms 59304 KB Output is correct
7 Correct 57 ms 59368 KB Output is correct
8 Correct 57 ms 59384 KB Output is correct
9 Correct 57 ms 59384 KB Output is correct
10 Correct 57 ms 59388 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 59256 KB Output is correct
2 Correct 59 ms 59256 KB Output is correct
3 Correct 57 ms 59512 KB Output is correct
4 Correct 58 ms 59256 KB Output is correct
5 Correct 58 ms 59312 KB Output is correct
6 Correct 58 ms 59304 KB Output is correct
7 Correct 57 ms 59368 KB Output is correct
8 Correct 57 ms 59384 KB Output is correct
9 Correct 57 ms 59384 KB Output is correct
10 Correct 57 ms 59388 KB Output is correct
11 Correct 127 ms 79196 KB Output is correct
12 Correct 64 ms 61304 KB Output is correct
13 Correct 86 ms 71036 KB Output is correct
14 Correct 185 ms 81556 KB Output is correct
15 Correct 112 ms 77484 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 59256 KB Output is correct
2 Correct 59 ms 59256 KB Output is correct
3 Correct 57 ms 59512 KB Output is correct
4 Correct 58 ms 59256 KB Output is correct
5 Correct 58 ms 59312 KB Output is correct
6 Correct 58 ms 59304 KB Output is correct
7 Correct 57 ms 59368 KB Output is correct
8 Correct 57 ms 59384 KB Output is correct
9 Correct 57 ms 59384 KB Output is correct
10 Correct 57 ms 59388 KB Output is correct
11 Correct 127 ms 79196 KB Output is correct
12 Correct 64 ms 61304 KB Output is correct
13 Correct 86 ms 71036 KB Output is correct
14 Correct 185 ms 81556 KB Output is correct
15 Correct 112 ms 77484 KB Output is correct
16 Correct 186 ms 108288 KB Output is correct
17 Correct 511 ms 125032 KB Output is correct
18 Correct 215 ms 110508 KB Output is correct
19 Correct 179 ms 108024 KB Output is correct
20 Correct 399 ms 116212 KB Output is correct