글 읽기 - 어디를 고쳐야 맞을까요

chungma900 6년 전 0

BFS로 하다가 계속 틀리길래 DP로 해봤는데 배열을 크게 하면 바로 반례가 생기네요.

DP[x][y][dir][visited] (x,y) 현재좌표이며 전에 dir방향으로 왔고 배달완료상태 visited로 식을정의하고 짰는데

4 4

S..C

....

C...

의경우 11이 맞는것같은데 13이 나오네요. 어디를 고치면 될지 잘모르겠습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>

using namespace std;

const int INF = 987654321;

int sx, sy;
int n, m;
char map[51][51];
int DP[51][51][5][1 << 2];
int dx[5] = { 0, 0,0,-1,1 };
int dy[5] = { 0, -1,1,0,0 };
int goal = (1 << 2) - 1;

int solve(int x, int y, int dir, int visited) {
	if (visited == goal) return 0;
	int &ret = DP[x][y][dir][visited];
	if (ret != -1) return ret;
	ret = INF;
	for (int k = 1; k <= 4; k++) {
		int xx = dx[k] + x;
		int yy = dy[k] + y;
		if (xx >= 0 && yy >= 0 && xx < n && yy < m && map[xx][yy] != '#' && dir != k) {
			if ((map[xx][yy] == '.' || map[xx][yy] == 'S')) {
				ret = min(ret, solve(xx, yy, k, visited) + 1);
			}
			else if (map[xx][yy] == 'C') {
				ret = min(ret, solve(xx, yy, k, visited | (1 << 0)) + 1);
			}
			else if (map[xx][yy] == 'c') {
				ret = min(ret, solve(xx, yy, k, visited | (1 << 1)) + 1);
			}
		}
	}
	return ret;
}

int main()
{
	bool finded = false;
	scanf("%d %d", &n, &m);

	memset(DP, -1, sizeof(DP));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %c", &map[i][j]);
			if (map[i][j] == 'S') {
				sx = i;
				sy = j;
			}
			if (map[i][j] == 'C' && !finded) {
				map[i][j] = 'c';
				finded = true;
			}
		}
	}

	int res = solve(sx, sy, 0, 0);
	if (res == INF) puts("-1");
	else printf("%d\n", res);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디를 고쳐야 맞을까요

chungma900 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말