SRM 272 DIV1 Hard ManhattanDistance

問題 Editorial

問題

画像が上手く表現できないので略

解答

(交差点の(x * y * (真ん中, 四隅)))でDPするだけ。
(width <= distance / 2)なので斜めに行く事はないので、(横か縦にいくつ進むか・交差点内の場所)をループしてやる。

コメント

これは一瞬で解けるべき

コード

#include <string>
#include <algorithm>
#include <cstring>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef pair<int,int> pii; 
typedef complex<double> P;
double dp[27][51][5];
struct ManhattanDistance {
	pii parse(string s) {
		int x = s[0] - 'A';
		int y = s[1] - '0';
		if(s.size() == 3) y = y * 10 + (s[2] - '0');
		y --;
		return mp(x, y);
	}
	double d, w;
	P pos(int x, int y, int i) {
		static const double dx[5] = {-.5, -1, 0, -1, 0}, dy[5] = {-.5, -1, -1, 0, 0};
		return P(x * d + w * dx[i], y * d - w * dy[i]);
	}
	pii sp, tp;
	double rec(int x, int y, int i) {
		if(dp[x][y][i] == dp[x][y][i]) return dp[x][y][i];
		double r = 1e10;
		if(x == tp.first && y == tp.second) {
			if(i == 0) r = 0;
		}else {
			P p = pos(x, y, i);
			rep(j, 5) {
				rer(xx, x+1, tp.first) r = min(r, abs(p - pos(xx, y, j)) + rec(xx, y, j));
				rer(yy, y+1, tp.second) r = min(r, abs(p - pos(x, yy, j)) + rec(x, yy, j));
			}
		}
		return dp[x][y][i] = r;
	}
	double minDistance(int distance, int width, string start, string target) {
		d = distance, w = width;
		sp = parse(start), tp = parse(target);
		mset(dp, -1);
		//x, yが増加方向に向かうように反転している
		if(sp.first > tp.first) sp.first = 26 - sp.first, tp.first = 26 - tp.first;
		if(sp.second > tp.second) sp.second = 50 - sp.second, tp.second = 50 - tp.second;
		return rec(sp.first, sp.second, 0);
	}
};