제출 #23603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
23603		gs14004	로봇 (APIO13_robots)	C++11	60 / 100	1500 ms	111960 KiB

robots

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40