oj.uz

Submission #258486

# Submission time Handle Problem Language Result Execution time Memory
258486 2020-08-06T04:31:34 Z pure_mem Robots (APIO13_robots) C++14
30 / 100
 1500 ms 106208 KB 
#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, len, 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();
		if(vals.X + len <= n)
			dp[vals.X][vals.X + len][pos.X][pos.Y] = min(dp[vals.X][vals.X + len][pos.X][pos.Y], dp[vals.X][vals.Y][pos.X][pos.Y] + dp[vals.Y + 1][vals.X + len][pos.X][pos.Y]);
		if(vals.Y - len >= 1)
			dp[vals.Y - len][vals.Y][pos.X][pos.Y] = min(dp[vals.Y - len][vals.Y][pos.X][pos.Y], dp[vals.X][vals.Y][pos.X][pos.Y] + dp[vals.Y - len][vals.X - 1][pos.X][pos.Y]);
		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(len = 1;len < n;len++){
		bfs();
		for(int A = 1, B = len + 1;B <= n;B++, A++){
				for(int x = 1;x <= h;x++){
					for(int y = 1;y <= w;y++){
						if(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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98552 KB Output is correct
2 Correct 50 ms 98552 KB Output is correct
3 Correct 52 ms 98552 KB Output is correct
4 Correct 49 ms 98808 KB Output is correct
5 Correct 50 ms 98808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98552 KB Output is correct
2 Correct 50 ms 98552 KB Output is correct
3 Correct 52 ms 98552 KB Output is correct
4 Correct 49 ms 98808 KB Output is correct
5 Correct 50 ms 98808 KB Output is correct
6 Correct 49 ms 98552 KB Output is correct
7 Correct 51 ms 98552 KB Output is correct
8 Correct 53 ms 98680 KB Output is correct
9 Correct 50 ms 98680 KB Output is correct
10 Correct 49 ms 98808 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98552 KB Output is correct
2 Correct 50 ms 98552 KB Output is correct
3 Correct 52 ms 98552 KB Output is correct
4 Correct 49 ms 98808 KB Output is correct
5 Correct 50 ms 98808 KB Output is correct
6 Correct 49 ms 98552 KB Output is correct
7 Correct 51 ms 98552 KB Output is correct
8 Correct 53 ms 98680 KB Output is correct
9 Correct 50 ms 98680 KB Output is correct
10 Correct 49 ms 98808 KB Output is correct
11 Execution timed out 1580 ms 106208 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98552 KB Output is correct
2 Correct 50 ms 98552 KB Output is correct
3 Correct 52 ms 98552 KB Output is correct
4 Correct 49 ms 98808 KB Output is correct
5 Correct 50 ms 98808 KB Output is correct
6 Correct 49 ms 98552 KB Output is correct
7 Correct 51 ms 98552 KB Output is correct
8 Correct 53 ms 98680 KB Output is correct
9 Correct 50 ms 98680 KB Output is correct
10 Correct 49 ms 98808 KB Output is correct
11 Execution timed out 1580 ms 106208 KB Time limit exceeded
12 Halted 0 ms 0 KB -