oj.uz

답안 #43308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43308 2018-03-13T12:24:33 Z mohammad_kilani 로봇 (APIO13_robots) C++14
0 / 100
 61 ms 67296 KB 
#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;
const int N = 510, MAX_COST = 500 * 75 * 9 + 2, oo = 2000000000;
char grid[N][N];
int n, m, k, dp[50][N][N], hsh[10][10], hashcnt = 0;
pair<int, int> go[4][N][N];
int dr[4] = { 0,1,0,-1 };
int dc[4] = { 1,0,-1,0 };

struct S {
	int r, c, low, high;
	S(int a, int b, int e, int d) { r = a, c = b, low = e, high = d; }
};

vector< S > pq[MAX_COST];

inline bool cangoto(int r, int c) {
	return (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] != 'x');
}

void make(int r, int c, int d) {
	int sr = r, sc = c;
	while (cangoto(r, c)) {
		go[d][r][c] = make_pair(sr, sc);
		if (grid[r][c] == 'C') d--; else if (grid[r][c] == 'A') d++;
		if (d == 4) d = 0;
		if (d == -1) d = 3;
		r += dr[d];
		c += dc[d];
	}
}

int main() {
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	memset(dp, -1, sizeof(dp));
	for (int i = 1;i <= 9;i++) {
		for (int j = i;j <= 9;j++) {
			hsh[i][j] = hashcnt++;
		}
	}
	memset(go, -1, sizeof(go));
	scanf("%d%d%d", &k, &m, &n);
	for (int i = 0;i < n;i++)
		scanf("%s", grid[i]);
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			if (grid[i][j] >= '1' && grid[i][j] <= '9') {
				pq[0].push_back(S(i, j, grid[i][j] - '0', grid[i][j] - '0'));
			}
			if (grid[i][j] == 'x') continue;
			for (int k = 0;k < 4;k++) {
				int nr = i + dr[k];
				int nc = j + dc[k];
				if (cangoto(nr, nc) == false) {
					make(i, j, (k + 2) % 4);
				}
			}
		}
	}
	int low, high, r, c, nr, nc, ans = oo;
	for (int i = 0;i < MAX_COST - 1;i++) {
		for (int j = 0;j < (int)pq[i].size();j++) {
			r = pq[i][j].r;
			c = pq[i][j].c;
			low = pq[i][j].low;
			high = pq[i][j].high;
			if (dp[hsh[low][high]][r][c] != -1)
				continue;
			if (low == 1 && high == k)
				ans = min(ans, i);
			dp[hsh[low][high]][r][c] = i;
			for (int j = 0;j < 4;j++) {
				nr = go[j][r][c].first;
				nc = go[j][r][c].second;
				if (dp[hsh[low][high]][nr][nc] == -1)
					pq[i + 1].push_back(S(nr, nc, low, high));
			}
			for (int j = low - 1;j >= 1;j--) {
				if (dp[hsh[j][low - 1]][r][c] != -1 && dp[hsh[j][high]][r][c] == -1)
					pq[i + dp[hsh[j][low - 1]][r][c]].push_back(S(r, c, j, high));
			}
			for (int j = high + 1;j <= k;j++) {
				if (dp[hsh[high + 1][j]][r][c] != -1 && dp[hsh[low][j]][r][c] == -1)
					pq[i + dp[hsh[high + 1][j]][r][c]].push_back(S(r, c, low, j));
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:46:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &k, &m, &n);
                             ^
robots.cpp:48:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", grid[i]);
                       ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 67192 KB Output is correct
2 Incorrect 54 ms 67296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 67192 KB Output is correct
2 Incorrect 54 ms 67296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 67192 KB Output is correct
2 Incorrect 54 ms 67296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 67192 KB Output is correct
2 Incorrect 54 ms 67296 KB Output isn't correct
3 Halted 0 ms 0 KB -