SRM 272 DIV1 Hard ManhattanDistance
問題
画像が上手く表現できないので略
解答
(交差点の(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); } };