Submission #258557

#	Time	Username	Problem	Language	Result	Execution time	Memory
258557		pure_mem	Robots (APIO13_robots)	C++14	30 / 100	202 ms	163840 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 = 10000 + 1, N = 501;
 
int n, len, w, h, a[N][N], dp[10][10][N][N];
pair<int, int> end_pos[5][N][N];
queue< pair<int, int> > q[inf];
queue< pair< int, pair< int, int > > > temp;
 
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++){
			if(a[x][y] == 13 || (x != 1 && x != h && y != 1 && y != w && a[x + 1][y] != 13 && a[x - 1][y] != 13 && a[x][y + 1] != 13 && a[x][y - 1] != 13))
				continue;
			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;
    				}
    				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(end_pos[dr][pos.X][pos.Y] != MP(0, 0)){
    					pos = end_pos[dr][pos.X][pos.Y];
    					break;
    				}
    				else{
    					temp.push(MP(dr, pos));
    				}
    				if(a[pos.X][pos.Y] == 12)
    					dr = (dr + 2) % 4 + 1;
    				else if(a[pos.X][pos.Y] == 11)
    					dr = dr % 4 + 1;
    			}
    			end_pos[bdr][x][y] = pos;
    			while(!temp.empty()){
    				end_pos[temp.front().X][temp.front().Y.X][temp.front().Y.Y] = pos;
    				temp.pop();	
    			} 
			}
		}			
	}
	int ans = inf;
	for(len = 1;len < n;len++){
		for(int A = 1;A + len - 1 <= n;A++){
			int B = A + len - 1;
			for(int x = 1;x <= h;x++){
				for(int y = 1;y <= w;y++){
					if(a[x][y] != 13 && dp[A][B][x][y] < inf)
						q[dp[A][B][x][y]].push(MP(x, y));	
				}
			}
			for(int it = 0;it < inf;it++){
				while(!q[it].empty()){
					pair<int, int> pos = q[it].front();
					q[it].pop();
					for(int dr = 1;dr <= 4;dr++){
						if(dp[A][B][end_pos[dr][pos.X][pos.Y].X][end_pos[dr][pos.X][pos.Y].Y] > dp[A][B][pos.X][pos.Y] + 1){
							dp[A][B][end_pos[dr][pos.X][pos.Y].X][end_pos[dr][pos.X][pos.Y].Y] = dp[A][B][pos.X][pos.Y] + 1;
							q[it + 1].push(end_pos[dr][pos.X][pos.Y]);
						}		
					}
				}
			}
		}
		for(int A = 1;A + len <= n;A++){
			for(int C = A;C < A + len;C++){
				for(int x = 1;x <= h;x++){
					for(int y = 1;y <= w;y++){
						if(a[x][y] != 13){
							dp[A][A + len][x][y] = min(dp[A][A + len][x][y], dp[A][C][x][y] + dp[C + 1][A + len][x][y]);
							if(A == 1 && A + len == n)
								ans = min(ans, dp[A][A + len][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