PKU 3328 Cliff Climbing

• ダイクストラ法
• [x座標][y座標][右足/左足]でコストを持たせる
• [左足x座標][左足y座標][右足x座標][右足y座標]だとTLEだった

const int dx[] = {1, 1, 1, 1, 1, 2, 2, 2, 3};
const int dy[] = {2, 1, 0, -1, -2, 1, 0, -1, 0};
static int dp[32][64][2];
static int s[32][64];

struct Node {
	int cost, x, y, lr;
	bool operator < (const Node& rh) const {
		return cost != rh.cost ? cost > rh.cost :
			x != rh.x ? x < rh.x :
			y != rh.y ? y < rh.y :
			lr < rh.lr;
	}
	Node(int cost, int x, int y, int lr) : cost(cost), x(x), y(y), lr(lr) { }
};

int in(int x, int y, int w, int h) {
	return 0 <= x && x < w && 0 <= y && y < h;
}

int main() {
	for (int w, h; cin >> w >> h && (w || h); ) {
		fill_n((int*)dp, sizeof(dp) / sizeof(int), INT_MAX / 3);

		// コスト, 左足x, 左足y, 右足x, 右足y
		priority_queue<Node> q;
		vector<pair<int, int> > goals;

		REP(y, h) {
			REP(x, w) {
				char c;
				cin >> c;
				if (c == 'S') {
					s[x][y] = 0;
					dp[x][y][0] = 0;
					dp[x][y][1] = 0;
					q.push(Node(0, x, y, 0));
					q.push(Node(0, x, y, 1));

				} else if (c == 'T') {
					goals.push_back(make_pair(x, y));
					s[x][y] = 0;

				} else if (c == 'X') {
					s[x][y] = INT_MAX / 3;

				} else {
					s[x][y] = c - '0';
				}
			}
		}

		while (!q.empty()) {
			Node current = q.top();
			q.pop();

			int cost;
			int x = current.x;
			int y = current.y;
			int lr = current.lr;

			if (dp[x][y][lr] != current.cost) {
				continue;
			}

			if (lr) {
				// 左足
				for (int dir = 0; dir < 9; ++dir) {
					x = current.x - dx[dir];
					y = current.y + dy[dir];

					if (!in(x, y, w, h)) {
						continue;
					}

					cost = current.cost + s[x][y];
					if (dp[x][y][0] <= cost) {
						continue;
					}

					dp[x][y][0] = cost;
					q.push(Node(cost, x, y, 0));
				}
			} else {
				// 右足
				for (int dir = 0; dir < 9; ++dir) {
					x = current.x + dx[dir];
					y = current.y + dy[dir];

					if (!in(x, y, w, h)) {
						continue;
					}

					cost = current.cost + s[x][y];
					if (dp[x][y][1] <= cost) {
						continue;
					}

					dp[x][y][1] = cost;
					q.push(Node(cost, x, y, 1));
				}
			}
		}

		int cost = INT_MAX / 3;
		for (vector<pair<int, int> >::iterator it = goals.begin(), itEnd = goals.end(); it != itEnd; ++it) {
			const int x = it->first;
			const int y = it->second;
			cost = min(cost, dp[x][y][0]);
			cost = min(cost, dp[x][y][1]);
		}

		if (cost >= INT_MAX / 3) {
			cost = -1;
		}

		cout << cost << endl;
	}
}