Submission #258568

#	Time	Username	Problem	Language	Result	Execution time	Memory
258568		pure_mem	Robots (APIO13_robots)	C++14	100 / 100	429 ms	125560 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 = 250000, N = 500;
 
char a[N][N];
int n, w, h, dp[9][9][N][N];
pair<int, int> end_pos[4][N][N];
vector< pair<int, int> > q[inf];
vector< 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 = 0;i < h;i++){
    	for(int j = 0;j < w;j++){
    		cin >> a[i][j];
    		if(a[i][j] >= '0' && a[i][j] <= '9'){
    			dp[a[i][j] - '0' - 1][a[i][j] - '0' - 1][i][j] = 0;	
    		}
    	}
    }
    for(int x = 0;x < h;x++){
    	for(int y = 0;y < w;y++){
    		if(a[x][y] == 'x')
    			continue;
    		for(int d = 0;d < 4;d++){
    			int dr = d;
    			if(a[x][y] == 'A')
    				dr = (dr + 3) % 4;
    			else if(a[x][y] == 'C')
    				dr = (dr + 1) % 4;
    			pair<int, int> pos = MP(x, y);
    			while(true){
    				if(dr == 0){
    					if(pos.X - 1 >= 0 && pos.X - 1 < h && pos.Y >= 0 && pos.Y < w && a[pos.X - 1][pos.Y] != 'x')
    						pos.X -= 1;
    					else
    						break;
    				}
    				else if(dr == 3){
    					if(pos.X >= 0 && pos.X < h && pos.Y - 1 >= 0 && pos.Y - 1 < w && a[pos.X][pos.Y - 1] != 'x')
    						pos.Y -= 1;
    					else
    						break;
    				}	
    				else if(dr == 2){
    					if(pos.X + 1 >= 0 && pos.X + 1 < h && pos.Y >= 0 && pos.Y < w && a[pos.X + 1][pos.Y] != 'x')
    						pos.X += 1;
    					else
    						break;
    				}             
    				else if(dr == 1){
    					if(pos.X >= 0 && pos.X < h && pos.Y + 1 >= 0 && pos.Y + 1 < w && a[pos.X][pos.Y + 1] != 'x')
    						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_back(MP(dr, pos));
    				} 
    				if(a[pos.X][pos.Y] == 'A')
    					dr = (dr + 3) % 4;
    				else if(a[pos.X][pos.Y] == 'C')
    					dr = (dr + 1) % 4;
    			}
    			end_pos[d][x][y] = pos;
    			while(!temp.empty()){
    				end_pos[temp.back().X][temp.back().Y.X][temp.back().Y.Y] = pos;
    				temp.pop_back();
    			}
    		}
    	}
    }

    int ans = inf;
    for(int len = 1;len < n;len++){
    	for(int A = 0;A + len - 1 < n;A++){
    		int B = A + len - 1;
    		for(int x = 0;x < h;x++){
   			 	for(int y = 0;y < w;y++){
                	if(a[x][y] != 'x' && dp[A][B][x][y] < inf){
                		q[dp[A][B][x][y]].push_back(MP(x, y));
                	}
    			}
    		}
    		for(int it = 0;it < inf;it++){
    			for(pair<int, int> pos: q[it]){
    				for(int dr = 0;dr < 4;dr++){
    					pair<int, int> to = end_pos[dr][pos.X][pos.Y];
    					if(dp[A][B][pos.X][pos.Y] + 1 < dp[A][B][to.X][to.Y]){
    						dp[A][B][to.X][to.Y] = dp[A][B][pos.X][pos.Y] + 1;	
    						if(it + 1 < inf)
    							q[it + 1].push_back(to);
    					}		
    				}
    		   }
    		   q[it].clear();
    		}
    	}
    	for(int A = 0;A + len < n;A++){
    		int B = A + len;
    		for(int x = 0;x < h;x++){
   			 	for(int y = 0;y < w;y++){
                	if(a[x][y] != 'x'){
                		for(int C = A;C < B;C++){
                			dp[A][B][x][y] = min(dp[A][B][x][y], dp[A][C][x][y] + dp[C + 1][B][x][y]);
                		}
                	}
    			}
    		}
    	}
    }
                                          /*
    cerr << end_pos[0][3][0].X << " " << end_pos[0][3][0].Y << "\n"; 
    cerr << dp[1][1][1][0] << "\n";         */

    for(int x = 0;x < h;x++){
    	for(int y = 0;y < w;y++){
    		if(a[x][y] != 'x')
    			ans = min(ans, dp[0][n - 1][x][y]);
    	}
    }
	                                            
	if(ans >= inf)
		ans = -1;
	cout << ans;
}

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