답안 #38950 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38950	2018-01-08T11:39:53 Z	qoo2p5	로봇 (APIO13_robots)	C++14	60 / 100	399 ms	75936 KB

robots

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
const ld EPS = (ld) 1e-7;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (int i = f; i < t; i++)
#define per(i, f, t) for (int i = f; i >= t; i--)

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (y > x) {
        x = y;
        return true;
    }
    return false;
}

void add(ll &x, ll y) {
	x += y;
	if (x >= MOD) x -= MOD;
	if (x < 0) x += MOD;
}

ll mult(ll x, ll y) {
	return x * y % MOD;
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

const int N = 10;
const int W = 303;
const int T = N * W * W;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int n, w, h;
int dp[N][N][W][W];
string f[W];
pair<pair<int, int>, int> step[W][W][4];
pair<int, int> nxt[W][W][4];
bool used[W][W];
vector<pair<int, int>> q[T];

bool can_go(int x, int y) {
	return 0 <= x && x < h && 0 <= y && y < w && f[x][y] != 'x';
}

void dfs(int x, int y, int dir) {
	if (nxt[x][y][dir].first != -3) {
		return;
	}
	
	if (step[x][y][dir].first.first == -1) {
		nxt[x][y][dir] = {x, y};
		return;
	}
	
	nxt[x][y][dir] = {-2, -2};
	int tx = step[x][y][dir].first.first;
	int ty = step[x][y][dir].first.second;
	int tdir = step[x][y][dir].second;
	if (nxt[tx][ty][tdir].first == -2) {
		nxt[x][y][dir] = {-1, -1};
		return;
	}
	
	dfs(tx, ty, tdir);
	if (nxt[tx][ty][tdir].first == -1) {
		nxt[x][y][dir] = {-1, -1};
		return;
	}
	
	nxt[x][y][dir] = nxt[tx][ty][tdir];
}

void run() {
	cin >> n >> w >> h;
	
	rep(i, 0, N) {
		rep(j, 0, N) {
			rep(t, 0, W) {
				rep(k, 0, W) {
					dp[i][j][t][k] = INF;
				}
			}
		}
	}
	
	rep(i, 0, h) {
		cin >> f[i];
		rep(j, 0, w) {
			if ('1' <= f[i][j] && f[i][j] <= '9') {
				int id = f[i][j] - '1';
				dp[id][id + 1][i][j] = 0;
			}
		}
	}
	
	rep(i, 0, h) {
		rep(j, 0, w) {
			rep(dir, 0, 4) {
				int tdir = dir;
				if (f[i][j] == 'A') {
					tdir = (tdir + 1) % 4;
				} else if (f[i][j] == 'C') {
					tdir = (tdir + 3) % 4;
				}
				int nx = i + dx[tdir];
				int ny = j + dy[tdir];
				if (!can_go(nx, ny)) {
					step[i][j][dir] = {{-1, -1}, -1};
				} else {
					step[i][j][dir] = {{nx, ny}, tdir};
				}
				
				nxt[i][j][dir] = {-3, -3};
			}
		}
	}
	
	rep(i, 0, h) {
		rep(j, 0, w) {
			rep(dir, 0, 4) {
				dfs(i, j, dir);
			}
		}
	}
		
	rep(len, 1, n + 1) {
		rep(l, 0, n - len + 1) {
			int r = l + len;
			rep(k, l + 1, r) {
				rep(x, 0, h) {
					rep(y, 0, w) {
						mini(dp[l][r][x][y], dp[l][k][x][y] + dp[k][r][x][y]);
					}
				}
			}
			
			memset(used, 0, sizeof used);
			rep(x, 0, h) {
				rep(y, 0, w) {
					if (dp[l][r][x][y] != INF) {
						q[dp[l][r][x][y]].pb({x, y});
					}
				}
			}
			
			rep(t, 0, T) {
				while (sz(q[t])) {
					int x = q[t].back().first;
					int y = q[t].back().second;
					q[t].pop_back();
					if (used[x][y]) {
						continue;
					}
					used[x][y] = 1;
				
					rep(dir, 0, 4) {
						int nx = nxt[x][y][dir].first;
						int ny = nxt[x][y][dir].second;
						if (nx != -1 && mini(dp[l][r][nx][ny], dp[l][r][x][y] + 1)) {
							q[dp[l][r][nx][ny]].pb({nx, ny});
						}
					}
				}
			}
		}
	}
	
	int ans = INF;
	rep(i, 0, h) {
		rep(j, 0, w) {
			mini(ans, dp[0][n][i][j]);
		}
	}
	cout << (ans == INF ? -1 : ans) << "\n";
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:72:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".in", "r", stdin);
                                        ^
robots.cpp:73:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(TASK ".out", "w", stdout);
                                          ^

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	66828 KB	Output is correct
2	Correct	26 ms	66828 KB	Output is correct
3	Correct	16 ms	66828 KB	Output is correct
4	Correct	26 ms	66828 KB	Output is correct
5	Correct	16 ms	66828 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	66828 KB	Output is correct
2	Correct	26 ms	66828 KB	Output is correct
3	Correct	16 ms	66828 KB	Output is correct
4	Correct	26 ms	66828 KB	Output is correct
5	Correct	16 ms	66828 KB	Output is correct
6	Correct	23 ms	66828 KB	Output is correct
7	Correct	29 ms	66828 KB	Output is correct
8	Correct	16 ms	66828 KB	Output is correct
9	Correct	16 ms	66828 KB	Output is correct
10	Correct	19 ms	66828 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	66828 KB	Output is correct
2	Correct	26 ms	66828 KB	Output is correct
3	Correct	16 ms	66828 KB	Output is correct
4	Correct	26 ms	66828 KB	Output is correct
5	Correct	16 ms	66828 KB	Output is correct
6	Correct	23 ms	66828 KB	Output is correct
7	Correct	29 ms	66828 KB	Output is correct
8	Correct	16 ms	66828 KB	Output is correct
9	Correct	16 ms	66828 KB	Output is correct
10	Correct	19 ms	66828 KB	Output is correct
11	Correct	239 ms	70928 KB	Output is correct
12	Correct	33 ms	67488 KB	Output is correct
13	Correct	119 ms	66960 KB	Output is correct
14	Correct	399 ms	75936 KB	Output is correct
15	Correct	206 ms	68188 KB	Output is correct

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	66828 KB	Output is correct
2	Correct	26 ms	66828 KB	Output is correct
3	Correct	16 ms	66828 KB	Output is correct
4	Correct	26 ms	66828 KB	Output is correct
5	Correct	16 ms	66828 KB	Output is correct
6	Correct	23 ms	66828 KB	Output is correct
7	Correct	29 ms	66828 KB	Output is correct
8	Correct	16 ms	66828 KB	Output is correct
9	Correct	16 ms	66828 KB	Output is correct
10	Correct	19 ms	66828 KB	Output is correct
11	Correct	239 ms	70928 KB	Output is correct
12	Correct	33 ms	67488 KB	Output is correct
13	Correct	119 ms	66960 KB	Output is correct
14	Correct	399 ms	75936 KB	Output is correct
15	Correct	206 ms	68188 KB	Output is correct
16	Runtime error	16 ms	66960 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Halted	0 ms	0 KB	-

답안 #38950

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 30.0 / 30.0

Subtask #4 0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
30.0 / 30.0

Subtask #4
0 / 40.0