BOJ)11983 Radio Contact

문제: icpc.me/11983

파머존과 소가 움직이는 경로가 주어질 때 파머존만 움직이거나 소만 움직이거나 둘이 동시에 움직일수 있다.

이동 후 둘의 거리의 제곱에 비례하게 라디오의 에너지가 소모될 때 파머존과 소가 목적지에 도착했을 때 소모된 라디오 에너지의 최솟값을 출력하는 문제이다.

우리는 이 문제를 다이나믹 프로그래밍을 통하여 해결할 수 있다.

dp[x][y]의 정의는 Farmer John이 X번 이동한 위치이고 소가 Y번 이동한 위치일 때까지 소모된 라디오 에너지의 최솟값이다.

점화식은 dp[x][y]=min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1])+dist(FJx ,COWy)가 되겠다.

파머존과 소가 한번도 움직이지 않았을 때는 에너지 소모가 없다고 하니 기저는 dp[0][0]=0이 된다.

#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
#define MAX_N 1000
#define INF 2100000000
using namespace std;
int dp[MAX_N + 1][MAX_N + 1], n, m;
pair<int, int> nx[MAX_N + 1], ny[MAX_N + 1];
char mx[MAX_N], my[MAX_N];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
map<char, int> mp;
int dist(pair<int, int> x, pair<int, int> y) {
    return (x.first - y.first)*(x.first - y.first) + (x.second - y.second)*(x.second - y.second);
}
int func(int x, int y) {
    if (x < 0 || y < 0)return INF;
    if (x == 0 && y == 0)return 0;
    int &ret = dp[x][y];
    if (ret != -1)return ret;
    return ret = min(func(x - 1, y), min(func(x, y - 1), func(x - 1, y - 1))) + dist(nx[x], ny[y]);
}
int main() {
    mp['N'] = 0;
    mp['S'] = 1;
    mp['E'] = 2;
    mp['W'] = 3;
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &nx[0].first, &nx[0].second, &ny[0].first, &ny[0].second);
    scanf("%s%s", &mx, &my);
    for (int i = 0; i < n; i++) {
        nx[i + 1].first = nx[i].first + dx[mp[mx[i]]];
        nx[i + 1].second = nx[i].second + dy[mp[mx[i]]];
    }
    for (int i = 0; i < m; i++) {
        ny[i + 1].first = ny[i].first + dx[mp[my[i]]];
        ny[i + 1].second = ny[i].second + dy[mp[my[i]]];
    }
    memset(dp, -1, sizeof(dp));
    printf("%d\n", func(n, m));
    return 0;
}