oj.uz

답안 #258503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258503 2020-08-06T04:57:32 Z pure_mem 로봇 (APIO13_robots) C++14
30 / 100
 1500 ms 106316 KB 
#include <bits/stdc++.h>
 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#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;
queue< pair< int, pair< int, int > > > temp;

void bfs(){
	while(!q.empty()){
		pair<int, int> pos = q.front().X, vals = q.front().Y;
		q.pop();
		if(vals.X + len <= n && vals.Y + 1 <= 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 && vals.X - 1 >= 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++){
			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;
    				//cerr << pos.X << " " << pos.Y << " " << x << " " << y << " " << dr << " " << bdr << " " << a[pos.X][pos.Y] << "\n";
    			}
    			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();	
    			} 
			}
		}			
	}
	//cerr << "was\n"; 
	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;
}

Compilation message

robots.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
robots.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 98552 KB Output is correct
2 Correct 49 ms 98552 KB Output is correct
3 Correct 51 ms 98552 KB Output is correct
4 Correct 49 ms 98808 KB Output is correct
5 Correct 49 ms 98808 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 98552 KB Output is correct
2 Correct 49 ms 98552 KB Output is correct
3 Correct 51 ms 98552 KB Output is correct
4 Correct 49 ms 98808 KB Output is correct
5 Correct 49 ms 98808 KB Output is correct
6 Correct 53 ms 98680 KB Output is correct
7 Correct 49 ms 98552 KB Output is correct
8 Correct 59 ms 98680 KB Output is correct
9 Correct 49 ms 98680 KB Output is correct
10 Correct 49 ms 98808 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 98552 KB Output is correct
2 Correct 49 ms 98552 KB Output is correct
3 Correct 51 ms 98552 KB Output is correct
4 Correct 49 ms 98808 KB Output is correct
5 Correct 49 ms 98808 KB Output is correct
6 Correct 53 ms 98680 KB Output is correct
7 Correct 49 ms 98552 KB Output is correct
8 Correct 59 ms 98680 KB Output is correct
9 Correct 49 ms 98680 KB Output is correct
10 Correct 49 ms 98808 KB Output is correct
11 Execution timed out 1579 ms 106316 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 98552 KB Output is correct
2 Correct 49 ms 98552 KB Output is correct
3 Correct 51 ms 98552 KB Output is correct
4 Correct 49 ms 98808 KB Output is correct
5 Correct 49 ms 98808 KB Output is correct
6 Correct 53 ms 98680 KB Output is correct
7 Correct 49 ms 98552 KB Output is correct
8 Correct 59 ms 98680 KB Output is correct
9 Correct 49 ms 98680 KB Output is correct
10 Correct 49 ms 98808 KB Output is correct
11 Execution timed out 1579 ms 106316 KB Time limit exceeded
12 Halted 0 ms 0 KB -