20240814

Sternhalma

我们给格子编个号,然后暴力打表出一个格子可以走到哪些点,然后状压 \(dp\),从全 \(1\) 的情况开始倒推,每次查询将其转化为二进制数列即可

#include <bits/stdc++.h>using namespace std;using pii = pair<int, int>;const int N = 21, M = (1 << 19);int q, n, a[N][N], len[] = {0, 3, 4, 5, 4, 3}, dp[N][M];vector<int> road1[N];vector<int> road2[N];char x[N][N];vector<int> v[21];bool check(int x, int y) {if (x < 1 || x > 5 || y < 1 || y > len[x]) {return false;}return true;
}int change(int x, int y) {int ans = 0;for (int i = 1; i < x; i++) {ans += len[i];}return ans + y;
}pii one_to_two(int x) {for (int i = 1; i <= 5; i++) {if (x <= len[i]) {return {i, x};}x -= len[i];}
}void Solve() {int cnt = 0, res = 0;for (int i = 1; i <= 5; i++) {for (int j = 1; j <= len[i]; j++) {cin >> x[i][j];cnt += (x[i][j] == '#');res += (1 << (change(i, j) - 1)) * (x[i][j] == '#');}}cout << dp[cnt][res] << "\n";
}int main() {ios::sync_with_stdio(0);cin.tie(0);for (int i = 0; i <= (1 << 19) - 1; i++) {int p = i, cnt = 0;while (p) {cnt += (p & 1);p >>= 1;}v[cnt].push_back(i);}road1[1].push_back(2), road1[1].push_back(4), road1[1].push_back(5);road2[1].push_back(3), road2[1].push_back(8), road2[1].push_back(10);road1[2].push_back(5), road1[2].push_back(6);road2[2].push_back(9), road2[2].push_back(11);roa d1[3].push_back(2), road1[3].push_back(6), road1[3].push_back(7);road2[3].push_back(1), road2[3].push_back(10), road2[3].push_back(12);road1[4].push_back(5), road1[4].push_back(9);road2[4].push_back(6), road2[4].push_back(14);road1[5].push_back(6), road1[5].push_back(10), road1[5].push_back(9);road2[5].push_back(7), road2[5].push_back(15), road2[5].push_back(13);road1[6].push_back(5), road1[6].push_back(10), road1[6].push_back(11);road2[6].push_back(4), road2[6].push_back(14), road2[6].push_back(16);road1[7].push_back(6), road1[7].push_back(11);road2[7].push_back(5), road2[7].push_back(15);road1[8].push_back(4), road1[8].push_back(9), road1[8].push_back(13);road2[8].push_back(1), road2[8].push_back(10), road2[8].push_back(17);road1[9].push_back(5), road1[9].push_back(10), road1[9].push_back(14);road2[9].push_back(2), road2[9].push_back(11), road2[9].push_back(18);road1[10].push_back(5), road1[10].push_back(6), road1[10].push_back(11);road2[10].push_back(1), road2[10].push_back(3), road2[10].push_back(12);road1[10].push_back(15), road1[10].push_back(14), road1[10].push_back(9);road2[10].push_back(19), road2[10].push_back(17), road2[10].push_back(8);road1[11].push_back(6), road1[11].push_back(10), road1[11].push_back(15);road2[11].push_back(2), road2[11].push_back(9), road2[11].push_back(18);road1[12].push_back(7), road1[12].push_back(11), road1[12].push_back(16);road2[12].push_back(3), road2[12].push_back(10), road2[12].push_back(19);road1[13].push_back(9), road1[13].push_back(14);road2[13].push_back(5), road2[13].push_back(15);road1[14].push_back(9), road1[14].push_back(10), road1[14].push_back(15);road2[14].push_back(4), road2[14].push_back(6), road2[14].push_back(16);road1[15].push_back(11), road1[15].push_back(10), road1[15].push_back(14);road2[15].push_back(7), road2[15].push_back(5), road2[15].push_back(13);road1[16].push_back(11), road1[16].push_back(15);road2[16].push_back(6), road2[16].push_back(14);road1[17].push_back(13), road1[17].push_back(14), road1[17].push_back(18);road2[17].push_back(8), road2[17].push_back(10), road2[17].push_back(19);road1[18].push_back(14), road1[18].push_back(15);road2[18].push_back(9), road2[18].push_back(11);road1[19].push_back(16), road1[19].push_back(15), road1[19].push_back(18);road2[19].push_back(12), road2[19].push_back(10), road2[19].push_back(17);for (int i = 1; i <= 5; i++) {for (int j = 1; j <= len[i]; j++) {cin >> a[i][j];}}memset(dp, 0xcf, sizeof(dp));dp[0][0] = 0;for (int i = 0; i < 19; i++) {for (auto j : v[i]) {for (int x = 1; x <= 19; x++) {if ((j & (1 << (x - 1)))) {continue;}dp[i + 1][j + (1 << (x - 1))] = max(dp[i + 1][j + (1 << (x - 1))], dp[i][j]);for (int l = 0; l < road1[x].size(); l++) {int tot1 = (1 << (road1[x][l] - 1));int tot2 = (1 << (road2[x][l] - 1));if (!(j & tot1) && (j & tot2)) {dp[i + 1][(j + tot1 + (1 << (x - 1))) - tot2] = max(dp[i + 1][(j + tot1 + (1 << (x - 1))) - tot2], dp[i][j] + a[one_to_two(road1[x][l]).first][one_to_two(road1[x][l]).second]);}}}}}cin >> q;while (q--) {Solve();}return 0;
}

Honeycomb

我们可以将每一个格子进行染色,至于如何染色我们可以找到如下这个字符

然后打表即可,假设我们只能自己走空格,那我们就可以用 \(bfs\) 答案就是经过了几个不同颜色的空格

#include <bits/stdc++.h>using namespace std;const int N = 6e3 + 5;struct node {int x, y, dis;
};int t, n, m, len[N], cnt, qx, qy, zx, zy;int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};bool vis[N][N];char a[N][N];int b[N][N];string s;void bfs() {deque<node> q;q.push_front({qx, qy, 1});while (!q.empty()) {node cur = q.front();q.pop_front();vis[cur.x][cur.y] = true;if (cur.x == zx && cur.y == zy) {cout << cur.dis << "\n";return ;}for (int i = 0; i < 4; i++) {int nx = cur.x + dx[i], ny = cur.y + dy[i];if (nx >= 1 && nx <= 3 + 4 * n && ny >= 1 && ny <= len[nx] && (a[nx][ny] == ' ' || a[nx][ny] == 'T') && !vis[nx][ny]) {if (b[nx][ny] != b[cur.x][cur.y]) {q.push_back({nx, ny, cur.dis + 1});}else q.push_front({nx, ny, cur.dis});}}}cout << "-1\n";
}void Solve() {cin >> n >> m;getline(cin, s);for (int i = 1; i <= 3 + n * 4; i++) {getline(cin, s);len[i] = s.size();for (int j = 0; j < s.size(); j++) {a[i][j + 1] = s[j];if (a[i][j + 1] == 'S') {qx = i, qy = j + 1;}else if (a[i][j + 1] == 'T') {zx = i, zy = j + 1;}}}cnt = 0;for (int i = 1; i <= n * 4; i++) {int tot = (i % 4) / 2;for (int j = 1; j <= len[i]; j++) {if (a[i][j] != '+') {continue;}tot++;if (!(tot % 2) || j == len[i]) {continue;}cnt++;b[i][j + 1] = b[i][j + 2] = b[i][j + 3] = cnt;b[i + 1][j - 1] = b[i + 1][j] = b[i + 1][j + 1] = b[i + 1][j + 2] = b[i + 1][j + 3] = b[i + 1][j + 4] = b[i + 1][j + 5] = cnt;b[i + 2][j - 2] = b[i + 2][j - 1] = b[i + 2][j] = b[i + 2][j + 1] = b[i + 2][j + 2] = b[i + 2][j + 3] = b[i + 2][j + 4] = b[i + 2][j + 5] = b[i + 2][j + 6] = cnt;b[i + 3][j - 1] = b[i + 3][j] = b[i + 3][j + 1] = b[i + 3][j + 2] = b[i + 3][j + 3] = b[i + 3][j + 4] = b[i + 3][j + 5] = cnt;b[i + 4][j + 1] = b[i + 4][j + 2] = b[i + 4][j + 3] = cnt;}}bfs();for (int i = 1; i <= 3 + 4 * n; i++) {for (int j = 1; j <= len[i]; j++) {vis[i][j] = false;b[i][j] = 0;a[i][j] = ' ';}}
}int main() {ios::sync_with_stdio(0);cin.tie(0);for (int i = 1; i < N; i++) {for (int j = 1; j < N; j++) {a[i][j] = ' ';}}cin >> t;while (t--) {Solve();}return 0;
}
/*+---+/12345\
+1234567+\12345/+---++---+       +---+/     \     /     \
+       +---+       +---+\           \     /     \+   +   S   +---+   T   +/     \     /           /
+       +---+       +   +\           \     /     \+---+       +---+       +/                       /
+       +---+       +   +\                 /     \+---+       +---+       +\     /     \     /+---+       +---+*/