[7975] 버스 여행

https://www.acmicpc.net/problem/7975 (AMPPZ 2012 B번)

어찌보면 흔한 BFS문제처럼 보일 수 있지만 "두 관광 명소 사이를 이동하는 와중에도 매력도가 100m마다 1씩 증가한다." 라는 조건때문에

도착점이 동일하더라도 시작하는 위치에 따라 cost가 바뀐다는 점을 해결하는 것이 이문제의 키포인트로 보인다.

결국 이 문제는 변수가 아래 두가지인 셈이다.

1. 현재위치와 다음위치 사이의 거리

2. 다음위치의 매력도

이 문제를 해결하기위해 생각해 본 것이 한가지 변수를 고정시키면 어떻게 풀 수 있는가 였다.

즉 2번 변수를 고정시켜 '만약 도시의 매력도가 모두 동일하다면 어떤점을 선택하는것이 유리할까' 라는 문제로 접근을 해보면, 

간단하게도 현재위치에서 갈수있는 다음위치들중 가장 먼 곳이 이 문제의 해답이다. 

현재 위치에서 가장 먼 점이라는 것은 다음위치로 갈수있는 점들 중 4모서리에 가장 가까운 네점중 하나가 우리가 원하는 최적해가 된다는 뜻이다.

2번 변수가 고정되어있지 않고 변한다고 해도, 이를 이용해 DP로 접근하면 답을 구할수 있다.

#include <stdio.h>

#include <vector>

#define ll long long

using namespace std;

struct st {

int r, c, idx; ll val, sum;

};

struct st2 {

int r, c, idx, val;

};

vector <st> vec[1000001];

st2 dat[1001][1001];

ll d[1001][1001] = { 0 };

int sign[4][2] = { 1,1,-1,1,1,-1,-1,-1 };

__inline ll max(ll a, ll b) {

return a > b ? a : b;

}

__inline ll ab(ll n) {

return n > 0 ? n : -n;

}

int main() {

int start = 1000000;

int end=0;

int n, m; scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i++)

{

for (int j = 1; j <= m; j++)

{

scanf("%d", &dat[i][j].idx);

dat[i][j].r = i;

dat[i][j].c = j;

if (dat[i][j].idx!=0 && dat[i][j].idx < start) start = dat[i][j].idx;

if (dat[i][j].idx > end) end = dat[i][j].idx;

}

}

for (int i = 1; i <= n; i++)

{

for (int j = 1; j <= m; j++)

{

scanf("%d", &dat[i][j].val);

st tmp;

tmp.r = dat[i][j].r;

tmp.c = dat[i][j].c;

tmp.val = dat[i][j].val;

tmp.idx = dat[i][j].idx;

vec[dat[i][j].idx].push_back(tmp);

}

}

st cand[4] = { 0 };

for (int i = 0; i < 4; i++) cand[i].sum = -987654321;

int last;

//dp시작

for (int j = start; j <= end; j++) {

if (vec[j].size() == 0) continue;

last = j;

//후보들로 d배열 갱신

for (int i = 0; i < vec[j].size(); i++)

{

int n_r = vec[j][i].r;

int n_c = vec[j][i].c;

for (int k = 0; k < 4; k++)

{

int r = cand[k].r;

int c = cand[k].c;

if (r == 0 || c == 0) continue;

ll v = cand[k].val;

d[n_r][n_c] = max(d[n_r][n_c], ab(n_r - r) + ab(n_c - c) + v);

}

d[n_r][n_c] += (ll)dat[n_r][n_c].val;

}

for (int i = 0; i < vec[j].size(); i++) {

//후보갱신

int r = vec[j][i].r;

int c = vec[j][i].c;

ll v = d[r][c];

ll s;

for (int k = 0; k < 4; k++) {

s = sign[k][0] * r + sign[k][1] * c + v;

if (s > cand[k].sum) {

cand[k].sum = s;

cand[k].r = r;

cand[k].c = c;

cand[k].val = v;

}

}

}

}

ll ans = 0;

for (int i = 0; i < vec[last].size(); i++) ans = max(ans, d[vec[last][i].r][vec[last][i].c]);

printf("%lld", ans);

}