NC23999. CSL 造迷宫
描述
输入描述
仅一行，有两个整数n, m，分别表示迷宫的长和宽。
输出描述
第一行输出一个整数，表示最长的距离。
之后输出一个 n 行 m 列的迷宫建造方案，其中用’X'表示障碍，‘.'表示空地。
示例1
输入:
2 8
输出:
11 .XXXX... ......X.
示例2
输入:
5 6
输出:
20 ...... XXXXX. ...... .XXXXX ......
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2019-11-23 19:05:21
#include <bits/stdc++.h>
using namespace std;
string ans[12][12][11];
void init();
int main() {
init();
int n, m;
cin >> n >> m;
char maze[12][12];
memset(maze, '.', sizeof (maze));
bool tran = false;
if (n < m) {
swap(n, m);
tran = true;
}
if (m < 6) {
if (m == 5) {
for (int i = 0; i != n; ++i) maze[i][1] = maze[i][3] = 'X';
maze[0][3] = '.';
maze[n - 1][1] = '.';
} else {
int p = (n - 1 & 3) + 1;
for (int i = n - p + 1; i != n; ++i) for (int j = 0; j != m - 1; ++j) maze[i][j] = 'X';
for (int i = 0; i != n - p; i += 4) {
for (int j = 0; j != m - 1; ++j) maze[i ^ 1][j] = 'X';
for (int j = 1; j != m ; ++j) maze[i ^ 3][j] = 'X';
}
}
} else {
for (int i = 0; i != n; ++i) for (int j = 0; j != m; ++j) maze[i][j] = ans[n][m][i][j];
}
if (tran) {
for (int i = 1; i != 12; ++i) for (int j = 0; j != i; ++j) swap(maze[i][j], maze[j][i]);
swap(n, m);
}
int cnt = 0;
for (int i = 0; i != n; ++i) {
maze[i][m] = '\0';
cnt += count(maze[i], maze[i] + m, '.');
}
cout << cnt << endl;
for (int i = 0; i != n; ++i) cout << maze[i] << endl;
}
void init() {
ans[11][11][0] = ".X...X.....";
ans[11][11][1] = ".X.X...XXX.";
ans[11][11][2] = ".X.XXXX....";
ans[11][11][3] = ".X...X..XXX";
ans[11][11][4] = "..XX.X.X...";
ans[11][11][5] = "X.X..X.X.X.";
ans[11][11][6] = "..X.X..X.X.";
ans[11][11][7] = ".X..X.X..X.";
ans[11][11][8] = ".X.X..X.X..";
ans[11][11][9] = ".X.X.XX.X.X";
ans[11][11][10]= "...X....X..";
ans[11][10][0] = ".X....X...";
ans[11][10][1] = ".X.XX.X.X.";
ans[11][10][2] = ".X.X..X.X.";
ans[11][10][3] = ".X.X.X..X.";
ans[11][10][4] = ".X.X.X.X..";
ans[11][10][5] = ".X.X...X.X";
ans[11][10][6] = "...XXXXX..";
ans[11][10][7] = "XXX.....X.";
ans[11][10][8] = "....XXX...";
ans[11][10][9] = ".XXX...XXX";
ans[11][10][10]= ".....X....";
ans[11][9][0] = ".X...X...";
ans[11][9][1] = "...X.X.X.";
ans[11][9][2] = "XXXX.X.X.";
ans[11][9][3] = "XX...X.X.";
ans[11][9][4] = "...XX..X.";
ans[11][9][5] = ".XX...X..";
ans[11][9][6] = "..X.XXX.X";
ans[11][9][7] = "X.X...X..";
ans[11][9][8] = "..XXX..X.";
ans[11][9][9] = ".X...X.X.";
ans[11][9][10]= "...X...X.";
ans[11][8][0] = ".X......";
ans[11][8][1] = "...XXXX.";
ans[11][8][2] = "XXX...X.";
ans[11][8][3] = "....X.X.";
ans[11][8][4] = ".XXX..X.";
ans[11][8][5] = ".XX..XX.";
ans[11][8][6] = "..X.XXX.";
ans[11][8][7] = "X.X...X.";
ans[11][8][8] = "..XXX...";
ans[11][8][9] = ".X...XXX";
ans[11][8][10]= "...X....";
ans[11][7][0] = ".X.....";
ans[11][7][1] = ".X.XXX.";
ans[11][7][2] = ".X...X.";
ans[11][7][3] = "..XX.X.";
ans[11][7][4] = "X.X..X.";
ans[11][7][5] = "..X.X..";
ans[11][7][6] = ".X..X.X";
ans[11][7][7] = ".X.XX..";
ans[11][7][8] = ".X...X.";
ans[11][7][9] = ".XXX.X.";
ans[11][7][10]= ".....X.";
ans[11][6][0] = "..X...";
ans[11][6][1] = "X.X.X.";
ans[11][6][2] = "..X.X.";
ans[11][6][3] = ".X..X.";
ans[11][6][4] = ".X.XX.";
ans[11][6][5] = ".X..X.";
ans[11][6][6] = ".XX.X.";
ans[11][6][7] = ".X..X.";
ans[11][6][8] = ".X.X..";
ans[11][6][9] = ".X.X.X";
ans[11][6][10]= "...X..";
ans[10][10][0] = ".X....X...";
ans[10][10][1] = "...XX.X.X.";
ans[10][10][2] = "XXX...X.X.";
ans[10][10][3] = "....XX..X.";
ans[10][10][4] = ".XXX...X..";
ans[10][10][5] = "...X.XXX.X";
ans[10][10][6] = "XX.X...X..";
ans[10][10][7] = "...XXX..X.";
ans[10][10][8] = ".XX...X.X.";
ans[10][10][9] = "....X...X.";
ans[10][9][0] = ".X...X...";
ans[10][9][1] = "...X.X.X.";
ans[10][9][2] = "XXX..X.X.";
ans[10][9][3] = "....X..X.";
ans[10][9][4] = ".XXX..X..";
ans[10][9][5] = "..XX.XX.X";
ans[10][9][6] = "X.XX..X..";
ans[10][9][7] = "..XXX..X.";
ans[10][9][8] = ".X...X.X.";
ans[10][9][9] = "...X...X.";
ans[10][8][0] = "...XX...";
ans[10][8][1] = "XX.X..X.";
ans[10][8][2] = "...X.X..";
ans[10][8][3] = ".XXX.X.X";
ans[10][8][4] = ".XX..X..";
ans[10][8][5] = "....XXX.";
ans[10][8][6] = "XXXX....";
ans[10][8][7] = ".....XXX";
ans[10][8][8] = ".XXXX...";
ans[10][8][9] = "......X.";
ans[10][7][0] = ".......";
ans[10][7][1] = "XXXXXX.";
ans[10][7][2] = "X......";
ans[10][7][3] = "..XXXXX";
ans[10][7][4] = ".X.....";
ans[10][7][5] = "...XXX.";
ans[10][7][6] = "XXX....";
ans[10][7][7] = "....XXX";
ans[10][7][8] = ".XXX...";
ans[10][7][9] = ".....X.";
ans[10][6][0] = ".X....";
ans[10][6][1] = ".X.XX.";
ans[10][6][2] = ".X..X.";
ans[10][6][3] = "..X.X.";
ans[10][6][4] = "X.X.X.";
ans[10][6][5] = "..X.X.";
ans[10][6][6] = ".X..X.";
ans[10][6][7] = ".X.X..";
ans[10][6][8] = ".X.X.X";
ans[10][6][9] = "...X..";
ans[9][9][0] = ".X...X...";
ans[9][9][1] = ".X.X.X.X.";
ans[9][9][2] = ".X.X...X.";
ans[9][9][3] = ".X..XXX..";
ans[9][9][4] = "..X.XXX.X";
ans[9][9][5] = "X.X...X..";
ans[9][9][6] = "..XXX..X.";
ans[9][9][7] = ".X...X.X.";
ans[9][9][8] = "...X...X.";
ans[9][8][0] = "....X...";
ans[9][8][1] = "XXX...X.";
ans[9][8][2] = "...XXX..";
ans[9][8][3] = ".X..XX.X";
ans[9][8][4] = "..X..X..";
ans[9][8][5] = "X.XX..X.";
ans[9][8][6] = "..XXX...";
ans[9][8][7] = ".X...XXX";
ans[9][8][8] = "...X....";
ans[9][7][0] = ".XX....";
ans[9][7][1] = ".XX.XX.";
ans[9][7][2] = "..X.X..";
ans[9][7][3] = "X.X.X.X";
ans[9][7][4] = "..X.X..";
ans[9][7][5] = ".X..XX.";
ans[9][7][6] = ".X.X...";
ans[9][7][7] = ".X.X.XX";
ans[9][7][8] = "...X...";
ans[9][6][0] = ".X....";
ans[9][6][1] = ".X.XX.";
ans[9][6][2] = ".X.X..";
ans[9][6][3] = ".X.X.X";
ans[9][6][4] = ".X.X..";
ans[9][6][5] = ".X.XX.";
ans[9][6][6] = ".X.X..";
ans[9][6][7] = ".X.X.X";
ans[9][6][8] = "...X..";
ans[8][8][0] = ".X......";
ans[8][8][1] = ".X.XXXX.";
ans[8][8][2] = ".X.XXXX.";
ans[8][8][3] = "...X....";
ans[8][8][4] = "XXX..XXX";
ans[8][8][5] = "....X...";
ans[8][8][6] = ".XXXX.X.";
ans[8][8][7] = "......X.";
ans[8][7][0] = ".X.....";
ans[8][7][1] = ".X.XXX.";
ans[8][7][2] = ".X...X.";
ans[8][7][3] = "..XX.X.";
ans[8][7][4] = "X.X..X.";
ans[8][7][5] = "..X.X..";
ans[8][7][6] = ".XX.X.X";
ans[8][7][7] = "....X..";
ans[8][6][0] = ".X....";
ans[8][6][1] = ".X.XX.";
ans[8][6][2] = ".X.X..";
ans[8][6][3] = ".X.X.X";
ans[8][6][4] = ".X.X..";
ans[8][6][5] = ".X..X.";
ans[8][6][6] = ".XX.X.";
ans[8][6][7] = "....X.";
ans[7][7][0] = ".X.....";
ans[7][7][1] = "...XXX.";
ans[7][7][2] = "XXX....";
ans[7][7][3] = "....XXX";
ans[7][7][4] = ".XXX...";
ans[7][7][5] = ".X...X.";
ans[7][7][6] = "...XXX.";
ans[7][6][0] = "..X...";
ans[7][6][1] = "X.X.X.";
ans[7][6][2] = "..X.X.";
ans[7][6][3] = ".X..X.";
ans[7][6][4] = ".X.X..";
ans[7][6][5] = ".X.X.X";
ans[7][6][6] = "...X..";
ans[6][6][0] = "......";
ans[6][6][1] = "XXXXX.";
ans[6][6][2] = "......";
ans[6][6][3] = ".XXXXX";
ans[6][6][4] = ".XX...";
ans[6][6][5] = "....X.";
}
C++11(clang++ 3.9) 解法, 执行用时: 827ms, 内存消耗: 125332K, 提交时间: 2019-11-29 15:46:27
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define Rep(i, n) for (int i = 1; i <=int(n); i++)
#define range(x) begin(x), end(x)
#ifdef __LOCAL_DEBUG__
#define _debug(fmt, ...) fprintf(stderr, "[%s] " fmt "\n", __func__, ##__VA_ARGS__)
#else
#define _debug(...) ((void) 0)
#endif
typedef long long LL;
typedef unsigned long long ULL;
enum {
OK = 0,
FORBID = 1,
CONN = 2
};
#define unsigned ULL
template <typename T> T update(T& x, T y) { return x = max(x, y); }
inline unsigned Get(unsigned x, int d) { return x >> (d * 3) & 7; }
inline unsigned Set(unsigned x, int d, unsigned v) {
d *= 3;
return (x & ~(7ull << d)) | v << d;
}
inline unsigned Set2(unsigned x, int d, int v1, int v2) {
return Set(Set(x, d, v1), d + 1, v2);
}
int n, m;
// state #dot prev ch
unordered_map<unsigned, tuple<int, unsigned, char>> dp[12][12];
inline unsigned Canon(unsigned x) {
int repr[8] = {0}, top = CONN;
for (int i = 0; i <= m; i++) {
int d = Get(x, i);
if (d < CONN) continue;
if (!repr[d]) repr[d] = top++;
x = Set(x, i, repr[d]);
}
return x;
}
inline unsigned Unite(unsigned x, int v1, int v2) {
for (int i = 0; i <= m; i++) if (Get(x, i) == v2) x = Set(x, i, v1);
return Canon(x);
}
char g[16][16];
int main() {
scanf("%d%d", &n, &m);
rep (i, n) {
if (i) {
for (auto pr : dp[i-1][m]) if (Get(pr.first, m) < 2) {
update(dp[i][0][Set(pr.first, m, 0) << 3],
make_tuple(get<0>(pr.second), pr.first, '\n'));
}
} else {
dp[0][0][CONN] = make_tuple(0, 0, '\n');
}
rep (j, m) {
for (auto pr : dp[i][j]) {
unsigned pre = pr.first; int val = get<0>(pr.second);
int d1 = Get(pre, j), d2 = Get(pre, j + 1);
if (d1 == OK and d2 == OK) {
update(dp[i][j+1][Canon(Set2(pre, j, 7, 7))],
make_tuple(val + 1, pre, '.'));
}
if (d1 < CONN and d2 < CONN) {
update(dp[i][j+1][Set2(pre, j, OK, OK)],
make_tuple(val, pre, 'X'));
}
if (d1 + d2 >= CONN and d1 * d2 == 0) {
int d = d1 + d2;
update(dp[i][j+1][Set2(pre, j, d, FORBID)],
make_tuple(val + 1, pre, '.'));
update(dp[i][j+1][Set2(pre, j, FORBID, d)],
make_tuple(val + 1, pre, '.'));
}
if (d1 >= CONN and d2 >= CONN and d1 != d2) {
unsigned mask = Unite(pre, d1, d2);
update(dp[i][j+1][Set2(mask, j, FORBID, FORBID)],
make_tuple(val + 1, pre, '.'));
}
}
}
}
unsigned last = 0; int val = 0;
for (auto pr : dp[n-1][m]) {
unsigned mask = pr.first; int v = get<0>(pr.second);
if (v <= val) continue;
if (Get(mask, m) != CONN) continue;
rep (i, m) if (Get(mask, i) >= CONN) goto fail;
last = mask; val = v;
fail:;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = m; j; j--) {
unsigned pre; char ch;
tie(ignore, pre, ch) = dp[i][j][last];
g[i][j-1] = ch;
last = pre;
}
last = get<1>(dp[i][0][last]);
}
printf("%d\n", val);
rep (i, n) puts(g[i]);
return 0;
}