Submission #258482

#	Time	Username	Problem	Language	Result	Execution time	Memory
258482		pure_mem	Robots (APIO13_robots)	C++14	30 / 100	1586 ms	106232 KiB

robots

#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

const int inf = 1e5 + 1, N = 501;

int n, w, h, a[N][N], dp[10][10][N][N];
pair<int, int> end_pos[5][N][N];
queue< pair< pair<int, int>, pair<int, int> > > q;

void bfs(){
	while(!q.empty()){
		pair<int, int> pos = q.front().X, vals = q.front().Y;
		q.pop();
		for(int i = 1;i <= 4;i++){
			if(dp[vals.X][vals.Y][end_pos[i][pos.X][pos.Y].X][end_pos[i][pos.X][pos.Y].Y] > dp[vals.X][vals.Y][pos.X][pos.Y] + 1){
				dp[vals.X][vals.Y][end_pos[i][pos.X][pos.Y].X][end_pos[i][pos.X][pos.Y].Y] = dp[vals.X][vals.Y][pos.X][pos.Y] + 1;
				q.push(MP(end_pos[i][pos.X][pos.Y], vals));
			}
		}
	}	
}

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	memset(dp, 0x3f, sizeof(dp));

	cin >> n >> w >> h;
	for(int i = 1;i <= h;i++){
		for(int j = 1;j <= w;j++){
			char x;
			cin >> x;
			if(x >= '0' && x <= '9'){
				a[i][j] = x - '0';
				dp[x - '0'][x - '0'][i][j] = 0;
				q.push(MP(MP(i, j), MP(a[i][j], a[i][j])));
			}
			else if(x == 'x'){
				a[i][j] = 13;
			}
			else if(x == 'A'){
				a[i][j] = 11;
			}
			else if(x == 'C'){
				a[i][j] = 12;
			}
			//cerr << a[i][j] << " "; 
		}
		//cerr << "\n";
	}
	if(n == 1)	
		return cout << 0, 0;
	for(int x = 1;x <= h;x++){
		for(int y = 1;y <= w;y++){
			for(int bdr = 1;bdr <= 4;bdr++){
    			pair<int, int> pos = MP(x, y);
    			int dr = bdr;
    			if(a[pos.X][pos.Y] == 12)
    				dr = (dr + 2) % 4 + 1;
    			else if(a[pos.X][pos.Y] == 11)
    				dr = dr % 4 + 1;
    			while(true){
    				if(dr == 1){
    					if(pos.X - 1 >= 1 && pos.X - 1 <= h && pos.Y >= 1 && pos.Y <= w && a[pos.X - 1][pos.Y] != 13)
    						pos.X -= 1;
    					else
    						break;
    				//	cerr << pos.X << " " << pos.Y << "\n";
    				}
    				else if(dr == 2){
    					if(pos.X >= 1 && pos.X <= h && pos.Y - 1 >= 1 && pos.Y - 1 <= w && a[pos.X][pos.Y - 1] != 13)
    						pos.Y -= 1;
    					else
    						break;
    				}	
    				else if(dr == 3){
    					if(pos.X + 1 >= 1 && pos.X + 1 <= h && pos.Y >= 1 && pos.Y <= w && a[pos.X + 1][pos.Y] != 13)
    						pos.X += 1;
    					else
    						break;
    				}
    				else{
    					if(pos.X >= 1 && pos.X <= h && pos.Y + 1 >= 1 && pos.Y + 1 <= w && a[pos.X][pos.Y + 1] != 13)
    						pos.Y += 1;
    					else
    						break;
    				}
    				if(a[pos.X][pos.Y] == 12)
    					dr = (dr + 2) % 4 + 1;
    				else if(a[pos.X][pos.Y] == 11)
    					dr = dr % 4 + 1;
    				//cerr << pos.X << " " << pos.Y << " " << x << " " << y << " " << dr << " " << bdr << " " << a[pos.X][pos.Y] << "\n";
    			}
    			end_pos[bdr][x][y] = pos; 
    			//cerr << "was";
			}
		}			
	}
	//cerr << 
	int ans = inf;
	for(int len = 1;len < n;len++){
		bfs();
		for(int A = 1, B = len + 1;B <= n;B++, A++){
			for(int C = A;C < B;C++){
				for(int x = 1;x <= h;x++){
					for(int y = 1;y <= w;y++){
						if(dp[A][B][x][y] > dp[A][C][x][y] + dp[C + 1][B][x][y]){
							dp[A][B][x][y] = dp[A][C][x][y] + dp[C + 1][B][x][y];
						}
						if(C + 1 == B && dp[A][B][x][y] < inf && len != n - 1)
							q.push(MP(MP(x, y), MP(A, B)));
						if(len == n - 1 && A == 1 && B == n){
							ans = min(ans, dp[A][B][x][y]); 
						}
					}
				}
			}
		}
	}                                            
	if(ans >= inf)
		ans = -1;
	cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40