oj.uz

답안 #23603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
23603 2017-05-15T11:37:52 Z gs14004 로봇 (APIO13_robots) C++11
60 / 100
 1500 ms 111960 KB 
#include <bits/stdc++.h>
using namespace std;

struct Pos{ int x, y; };
struct Dat{
	Pos p; int d;
	bool operator<(const Dat &oth) const { return d < oth.d; }
};

const int inf = 1e9, dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int n, h, w, x[10], y[10], md[502][502][10][10], c[10][10], s[502][502], ans = inf;
char b[502][502];
Pos dp[502][502][4];
vector<Dat> v;
queue<Pos> q;

int get(int a, int b, int c, int d){
	if(a > c) swap(a, c);
	if(b > d) swap(b, d);
	return s[c][d] - s[a - 1][d] - s[c][b - 1] + s[a - 1][b - 1];
}

int av(const Pos &p){ return (p.x > 0) && (p.y > 0) && (p.x <= h) && (p.y <= w) && (b[p.x][p.y] != 'x'); }

Pos wh(Pos p, int d){
	if(dp[p.x][p.y][d].x != 0) return dp[p.x][p.y][d];
    int s = 1, e = max(w, h);
	while(s <= e){
		int m = (s + e) / 2;
        int nx = p.x + dx[d] * m, ny = p.y + dy[d] * m;
        if(!av({nx, ny}) || get(p.x + dx[d], p.y + dy[d], nx, ny)) e = m - 1;
        else s = m + 1;
	}
	int nx = p.x + dx[d] * s, ny = p.y + dy[d] * s;
    if(!av({nx, ny})){
		nx -= dx[d]; ny -= dy[d];
		dp[p.x][p.y][d] = {nx, ny};
    }
    else{
		dp[p.x][p.y][d] = wh({nx, ny}, (d + b[nx][ny] - 'A' + 1) % 4);
    }
    return dp[p.x][p.y][d];
}

void dnc(int s, int e){
	if(c[s][e]) return;
	c[s][e] = 1;
	for(int k = s; k < e; k++){
		dnc(s, k); dnc(k + 1, e);
		for(int i = 1; i <= h; i++){
			for(int j = 1; j <= w; j++){
                md[i][j][s][e] = min(md[i][j][s][e], md[i][j][s][k] + md[i][j][k + 1][e]);
			}
		}
	}
	v.clear();
	for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) if(md[i][j][s][e] < inf) v.push_back({{i, j}, md[i][j][s][e]});
	sort(v.begin(), v.end());
	for(auto &cur : v){
		if(cur.d != md[cur.p.x][cur.p.y][s][e]) continue;
		q.push(cur.p);
		while(!q.empty()){
			Pos cp = q.front(); q.pop();
			int nd = md[cp.x][cp.y][s][e] + 1;
			for(int i = 0; i < 4; i++){
				Pos np = wh(cp, i);
				if(md[np.x][np.y][s][e] > nd){
					md[np.x][np.y][s][e] = nd;
					q.push(np);
				}
			}
		}
	}
}

int main(){
	scanf("%d%d%d", &n, &w, &h);
	for(int i = 1; i <= h; i++){
		scanf("%s", b[i] + 1);
		for(int j = 1; j <= w; j++){
            if('1' <= b[i][j] && b[i][j] <= '9'){
				x[b[i][j] - '0'] = i;
				y[b[i][j] - '0'] = j;
            }
            else if(b[i][j] != '.') s[i][j]++;
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	}
	for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) for(int k = 1; k <= n; k++) for(int l = k; l <= n; l++)
		md[i][j][k][l] = inf;
    for(int i = 1; i <= n; i++){
		md[x[i]][y[i]][i][i] = 0;
    }
    dnc(1, n);
    for(int i = 1; i <= h; i++) for(int j = 1; j <= w; j++) ans = min(ans, md[i][j][1][n]);
    printf("%d\n", ans == inf ? -1 : ans);
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:77:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &w, &h);
                             ^
robots.cpp:79:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", b[i] + 1);
                        ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 109572 KB Output is correct
2 Correct 0 ms 109572 KB Output is correct
3 Correct 0 ms 109572 KB Output is correct
4 Correct 0 ms 109572 KB Output is correct
5 Correct 0 ms 109572 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 109572 KB Output is correct
2 Correct 0 ms 109572 KB Output is correct
3 Correct 0 ms 109572 KB Output is correct
4 Correct 0 ms 109572 KB Output is correct
5 Correct 0 ms 109572 KB Output is correct
6 Correct 0 ms 109572 KB Output is correct
7 Correct 0 ms 109572 KB Output is correct
8 Correct 0 ms 109572 KB Output is correct
9 Correct 0 ms 109572 KB Output is correct
10 Correct 0 ms 109572 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 109572 KB Output is correct
2 Correct 0 ms 109572 KB Output is correct
3 Correct 0 ms 109572 KB Output is correct
4 Correct 0 ms 109572 KB Output is correct
5 Correct 0 ms 109572 KB Output is correct
6 Correct 0 ms 109572 KB Output is correct
7 Correct 0 ms 109572 KB Output is correct
8 Correct 0 ms 109572 KB Output is correct
9 Correct 0 ms 109572 KB Output is correct
10 Correct 0 ms 109572 KB Output is correct
11 Correct 336 ms 110232 KB Output is correct
12 Correct 23 ms 109572 KB Output is correct
13 Correct 103 ms 109572 KB Output is correct
14 Correct 579 ms 110808 KB Output is correct
15 Correct 266 ms 109940 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 109572 KB Output is correct
2 Correct 0 ms 109572 KB Output is correct
3 Correct 0 ms 109572 KB Output is correct
4 Correct 0 ms 109572 KB Output is correct
5 Correct 0 ms 109572 KB Output is correct
6 Correct 0 ms 109572 KB Output is correct
7 Correct 0 ms 109572 KB Output is correct
8 Correct 0 ms 109572 KB Output is correct
9 Correct 0 ms 109572 KB Output is correct
10 Correct 0 ms 109572 KB Output is correct
11 Correct 336 ms 110232 KB Output is correct
12 Correct 23 ms 109572 KB Output is correct
13 Correct 103 ms 109572 KB Output is correct
14 Correct 579 ms 110808 KB Output is correct
15 Correct 266 ms 109940 KB Output is correct
16 Correct 1016 ms 109572 KB Output is correct
17 Execution timed out 1500 ms 111960 KB Execution timed out
18 Halted 0 ms 0 KB -