PKU 1826 The Best Farm

• 深さ優先探索
• タイルを二次元配列で持たせることができないのでハッシュマップを使って持たせている
• 時間がギリギリのためscanf()を使用した

#ifdef _MSC_VER
#include <hash_set>
#include <hash_map>
using namespace stdext;
#else
#include <ext/hash_set>
#include <ext/hash_map>
using namespace __gnu_cxx;
#endif

using namespace std;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);
typedef long long ll;

typedef complex<int> P;

namespace std {
	inline bool operator < (const P& lh , const P& rh) {
		return lh.real() != rh.real() ? lh.real() < rh.real() : lh.imag() < rh.imag();
	}
}

namespace stdext {
	inline size_t hash_value(const P& rh)
	{
		return rh.real() * 65536 + rh.imag();
	}

}

const P ps[] = {P(0, 1), P(0, -1), P(-1, 0), P(1, 0)};

int main() {
	for (int N; scanf("%d", &N), N; ) {
		hash_map<P, int> m;
		for (int n = 0; n < N; ++n) {
			int x, y, value;
			scanf("%d%d%d", &x, &y, &value);
			m[P(x, y)] = value;
		}

		set<P> visited;
		int bestAnswer = -1;
		for (hash_map<P, int>::iterator it = m.begin(), itEnd = m.end(); it != itEnd; ++it) {
			if (visited.count(it->first)) {
				continue;
			}
			visited.insert(it->first);

			int answer = 0;
			vector<P> q;
			q.push_back(it->first);
			while (!q.empty()) {
				const P p = q.back();
				q.pop_back();

				answer += m[p];

				for (int dir = 0; dir < 4; ++dir) {
					const P pp = p + ps[dir];
					if (!m.count(pp) || visited.count(pp)) {
						continue;
					}

					visited.insert(pp);
					q.push_back(pp);
				}
			}

			bestAnswer = max(bestAnswer, answer);
		}

		printf("%d\n", bestAnswer);
	}
}
<||

*1274185070*PKU 1691 Painting A Board
-ダイクストラ法
-あらかじめ、このタイルを塗るにはこのタイルが塗られていなければならないというテーブルを持たせる
-dp[どのタイルを塗ったか][最後に塗った色]でダイクストラ法
>|cpp|
struct Board {
	int left, top, right, bottom, color;
	bool needs(const Board& rh) const {
		return top == rh.bottom && left < rh.right && rh.left < right;
	}
};

static int dp[1 << 15][32];

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

int main() {
	int needs[16];
	Board boards[16];

	int M;
	cin >> M;
	for (int m = 0; m < M; ++m) {
		int N;
		cin >> N;
		for (int n = 0; n < N; ++n) {
			Board& board = boards[n];
			cin >> board.top >> board.left >> board.bottom >> board.right >> board.color;
		}

		memset(needs, 0, sizeof(needs));

		for (int top = 0; top < N; ++top) {
			for (int bottom = 0; bottom < N; ++bottom) {
				if (boards[bottom].needs(boards[top])) {
					needs[bottom] |= (1 << top);
				}
			}
		}

		fill_n((int*)dp, sizeof(dp) / sizeof(dp[0][0]), INT_MAX / 2);

		priority_queue<Node> q;
		q.push(Node(0, 0, 0));
		dp[0][0] = 0;

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

			if (dp[node.flag][node.color] != node.cost) {
				continue;
			}

			for (int to = 0; to < N; ++to) {
				if (node.flag & (1 << to)) {
					continue;
				}

				if ((node.flag & needs[to]) != needs[to]) {
					continue;
				}

				const int nextFlag = node.flag | (1 << to);
				const int nextColor = boards[to].color;
				const int nextCost = node.cost + (boards[to].color != node.color ? 1 : 0);
				if (dp[nextFlag][nextColor] <= nextCost) {
					continue;
				}

				dp[nextFlag][nextColor] = nextCost;
				q.push(Node(nextFlag, nextColor, nextCost));
			}
		}

		int bestAnswer = INT_MAX;
		for (int color = 0; color < 32; ++color) {
			bestAnswer = min(bestAnswer, dp[(1 << N) - 1][color]);
		}
		cout << bestAnswer << endl;
	}
}