You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
81 lines
1.7 KiB
81 lines
1.7 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
const int N = 110;
|
|
int dx[] = {-1, 0, 1, 0};
|
|
int dy[] = {0, 1, 0, -1};
|
|
|
|
struct Node {
|
|
int x, y;
|
|
} b[N];
|
|
int bl;
|
|
|
|
char a[N][N];
|
|
int n, m;
|
|
vector<string> path;
|
|
int res;
|
|
|
|
void dfs(int u, int sum) {
|
|
if (u == bl + 1) {
|
|
if (sum > res) path.clear();
|
|
if (sum >= res) {
|
|
string t = "";
|
|
for (int i = 1; i <= n; i++)
|
|
for (int j = 1; j <= m; j++)
|
|
t += a[i][j];
|
|
path.push_back(t);
|
|
}
|
|
res = max(res, sum);
|
|
return;
|
|
}
|
|
|
|
dfs(u + 1, sum);
|
|
|
|
int f = 1;
|
|
|
|
Node c[N];
|
|
int cl = 0;
|
|
|
|
int cx = b[u].x, cy = b[u].y;
|
|
for (int i = 0; i < 4; i++) {
|
|
int tx = dx[i] + cx, ty = dy[i] + cy;
|
|
if (tx <= 0 || tx > n || ty <= 0 || ty > m) continue;
|
|
if (a[tx][ty] == 'C' || a[tx][ty] == 'D' || a[tx][ty] == 'Z') return;
|
|
c[++cl] = {tx, ty};
|
|
}
|
|
|
|
if (f) {
|
|
a[cx][cy] = 'Z';
|
|
for (int i = 1; i <= cl; i++) a[c[i].x][c[i].y] += 2;
|
|
|
|
dfs(u + 1, sum + cl + 1);
|
|
|
|
a[cx][cy] = 'B';
|
|
for (int i = 1; i <= cl; i++) a[c[i].x][c[i].y] -= 2;
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
freopen("5.in", "r", stdin);
|
|
|
|
cin >> n >> m;
|
|
for (int i = 1; i <= n; i++)
|
|
for (int j = 1; j <= m; j++) {
|
|
cin >> a[i][j];
|
|
if (a[i][j] == 'B') b[++bl] = {i, j};
|
|
}
|
|
|
|
dfs(1, 0);
|
|
|
|
cout << res << endl;
|
|
|
|
for (int i = 0; i < (int)path.size(); i++) {
|
|
for (int j = 0; j < (int)path[i].size(); j++) {
|
|
cout << path[i][j] << " ";
|
|
if ((j + 1) % m == 0) cout << endl;
|
|
}
|
|
cout << endl;
|
|
}
|
|
|
|
return 0;
|
|
} |