P4205智慧珠游戏
纯暴力， 没啥讲的，码农题。
注意分类，优先选择上面行，左边列的点建图。
题目链接
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
ll g[110][110], vis[30], tim;
bool ok() {
bool flag = 1;
for (ll i = 1; i <= 10; i++) {
for (ll j = 1; j <= i; j++) {
if (g[i][j] == 0) {
flag = 0;
}
}
}
return flag;
}
ll gtn(char x) {
return x - 'A' + 1;
}
char gtc(ll x) {
return x - 1 + 'A';
}
bool cant(ll x, ll y) {
return g[x][y] != 0;
}
namespace a {
ll num = 4, cnt = 3;
ll gx[4][3] = {{0, 0, 1}, {0, 0, 1}, {0, 1, 1}, {0, 1, 1}};
ll gy[4][3] = {{0, 1, 0}, {0, 1, 1}, {0, 1, 0}, {0, -1, 0}};
};
namespace b {
ll num = 2, cnt = 4;
ll gx[2][4] = {{0, 0, 0, 0}, {0, 1, 2, 3}};
ll gy[2][4] = {{0, 1, 2, 3}, {0, 0, 0, 0}};
};
namespace c {
ll num = 8, cnt = 4;
ll gx[8][4] = {{0, 0, 0, 1}, {0, 0, 0, 1}, {0, 1, 1, 1}, {0, 1, 1, 1}, {0, 0, 1, 2}, {0, 0, 1, 2}, {0, 1, 2, 2}, {0, 1, 2, 2}};
ll gy[8][4] = {{0, 1, 2, 0}, {0, 1, 2, 2}, {0, 1, 2, 0}, {0, -2, -1, 0}, {0, 1, 0, 0}, {0, 1, 1, 1}, {0, 0, 0, 1}, {0, 0, 0, -1}};
};
namespace d {
ll num = 1, cnt = 4;
ll gx[1][4] = {{0, 0, 1, 1}};
ll gy[1][4] = {{0, 1, 0, 1}};
};
namespace e {
ll num = 4, cnt = 5;
ll gx[4][5] = {{0, 0, 0, 1, 2}, {0, 0, 0, 1, 2}, {0, 1, 2, 2, 2}, {0, 1, 2, 2, 2}};
ll gy[4][5] = {{0, 1, 2, 0, 0}, {0, 1, 2, 2, 2}, {0, 0, 0, 1, 2}, {0, 0, 0, -1, -2}};
};
namespace f{
ll num = 8, cnt = 5;
ll gx[8][5] = {{0, 0, 0, 0, 1}, {0, 0, 0, 0, 1}, {0, 1, 1, 1, 1}, {0, 1, 1, 1, 1}, {0, 1, 2, 3, 2}, {0, 1, 2, 3, 2}, {0, 1, 2, 3, 1}, {0, 1, 2, 3, 1}};
ll gy[8][5] = {{0, 1, 2, 3, 1}, {0, 1, 2, 3, 3}, {0, -1, 0, 1, 2}, {0, 1, 0, -1, -2}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, -1}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, -1}};
};
namespace gg {
ll num = 4, cnt = 5;
ll gx[4][5] = {{0, 0, 0, 1, 1}, {1, 1, 1, 0, 0}, {0, 0, 1, 2, 2}, {0, 0, 1, 2, 2}};
ll gy[4][5] = {{0, 1, 2, 0, 2}, {0, 1, 2, 0, 2}, {0, 1, 0, 0, 1}, {0, 1, 1, 0, 1}};
};
namespace h {
ll num = 8, cnt = 5;
ll gx[8][5] = {{0, 0, 0, 1, 1}, {0, 0, 0, 1, 1}, {0, 0, 1, 1, 1}, {0, 0, 1, 1, 1}, {0, 0, 1, 1, 2}, {0, 0, 1, 1, 2}, {0, 1, 1, 2, 2}, {0, 1, 1, 2, 2}};
ll gy[8][5] = {{0, 1, 2, 0, 1}, {0, 1, 2, 1, 2}, {0, 1, 0, 1, 2}, {0, 1, -1, 0, 1}, {0, 1, 0, 1, 0}, {0, 1, 0, 1, 1}, {0, 0, 1, 0, 1}, {0, 0, -1, 0, -1}};
};
namespace ii {
ll num = 8, cnt = 5;
ll gx[8][5] = {{0, 0, 0, 1, 1}, {0, 0, 0, 1, 1}, {0, 0, 1, 1, 1}, {0, 0, 1, 1, 1}, {0, 1, 2, 2, 3}, {0, 1, 2, 2, 3}, {0, 1, 1, 2, 3}, {0, 1, 1, 2, 3}};
ll gy[8][5] = {{0, 1, 2, 2, 3}, {0, 1, 2, -1, 0}, {0, 1, 0, -1, -2}, {0, 1, 1, 2, 3}, {0, 0, 0, -1, -1}, {0, 0, 0, 1, 1}, {0, 0, 1, 1, 1}, {0, 0, -1, -1, -1}};
};
namespace jj {
ll num = 1, cnt = 5;
ll gx[1][5] = {{0, 1, 1, 1, 2}};
ll gy[1][5] = {{0, -1, 0, 1, 0}};
};
namespace kk {
ll num = 4, cnt = 5;
ll gx[4][5] = {{0, 1, 1, 2, 2}, {0, 1, 1, 2, 2}, {0, 0, 1, 1, 2}, {0, 0, 1, 1, 2}};
ll gy[4][5] = {{0, 0, 1, 1, 2}, {0, 0, -1, -1, -2}, {0, 1, 0, -1, -1}, {0, 1, 1, 2, 2}};
};
namespace l {
ll num = 8, cnt = 5;
ll gx[8][5] = {{1, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {0, 1, 1, 1, 1}, {0, 1, 1, 1, 1}, {0, 0, 1, 2, 3}, {0, 0, 1, 2, 3}, {0, 1, 2, 3, 3}, {0, 1, 2, 3, 3}};
ll gy[8][5] = {{0, 1, 2, 3, 0}, {0, 1, 2, 3, 3}, {0, 1, 2, 3, 0}, {0, 0, -1, -2, -3}, {0, 1, 0, 0, 0}, {0, 1, 1, 1, 1}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, -1}};
};
void dfs(ll cnt) {
tim++;
if (tim > 3000000) {
printf("No solution");
exit(0);
}
if (cnt > 12) {
if (ok()) {
for (ll i = 1; i <= 10; i++) {
for (ll j = 1; j <= i; j++) {
printf("%c", gtc(g[i][j]));
}
printf("\n");
}
}
exit(0);
}
/*for (ll i = 1; i <= 10; i++) {
for (ll j = 1; j <= i; j++) {
if (g[i][j])
printf("%c", gtc(g[i][j]));
else
printf(".");
}
printf("\n");
}
printf("\n");*/
ll x, y;
for (ll i = 1; i <= 10; i++) {
bool flag = 0;
for (ll j = 1; j <= i; j++) {
if (g[i][j] == 0) {
x = i, y = j;
flag = 1;
break;
}
}
if (flag) break;
}
if (!vis[gtn('A')]) {
for (ll i = 0; i < a::num; i++) {
bool flag = 0;
for (ll j = 0; j < a::cnt; j++) {
if (cant(x+a::gx[i][j], y+a::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < a::cnt; j++) {
g[x+a::gx[i][j]][y+a::gy[i][j]] = gtn('A');
}
vis[gtn('A')] = 1;
dfs(cnt+1);
vis[gtn('A')] = 0;
for (ll j = 0; j < a::cnt; j++) {
g[x+a::gx[i][j]][y+a::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('B')]) {
for (ll i = 0; i < b::num; i++) {
bool flag = 0;
for (ll j = 0; j < b::cnt; j++) {
if (cant(x+b::gx[i][j], y+b::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < b::cnt; j++) {
g[x+b::gx[i][j]][y+b::gy[i][j]] = gtn('B');
}
vis[gtn('B')] = 1;
dfs(cnt+1);
vis[gtn('B')] = 0;
for (ll j = 0; j < b::cnt; j++) {
g[x+b::gx[i][j]][y+b::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('C')]) {
for (ll i = 0; i < c::num; i++) {
bool flag = 0;
for (ll j = 0; j < c::cnt; j++) {
if (cant(x+c::gx[i][j], y+c::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < c::cnt; j++) {
g[x+c::gx[i][j]][y+c::gy[i][j]] = gtn('C');
}
vis[gtn('C')] = 1;
dfs(cnt+1);
vis[gtn('C')] = 0;
for (ll j = 0; j < c::cnt; j++) {
g[x+c::gx[i][j]][y+c::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('D')]) {
for (ll i = 0; i < d::num; i++) {
bool flag = 0;
for (ll j = 0; j < d::cnt; j++) {
if (cant(x+d::gx[i][j], y+d::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < d::cnt; j++) {
g[x+d::gx[i][j]][y+d::gy[i][j]] = gtn('D');
}
vis[gtn('D')] = 1;
dfs(cnt+1);
vis[gtn('D')] = 0;
for (ll j = 0; j < d::cnt; j++) {
g[x+d::gx[i][j]][y+d::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('E')]) {
for (ll i = 0; i < e::num; i++) {
bool flag = 0;
for (ll j = 0; j < e::cnt; j++) {
if (cant(x+e::gx[i][j], y+e::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < e::cnt; j++) {
g[x+e::gx[i][j]][y+e::gy[i][j]] = gtn('E');
}
vis[gtn('E')] = 1;
dfs(cnt+1);
vis[gtn('E')] = 0;
for (ll j = 0; j < e::cnt; j++) {
g[x+e::gx[i][j]][y+e::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('F')]) {
for (ll i = 0; i < f::num; i++) {
bool flag = 0;
for (ll j = 0; j < f::cnt; j++) {
if (cant(x+f::gx[i][j], y+f::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < f::cnt; j++) {
g[x+f::gx[i][j]][y+f::gy[i][j]] = gtn('F');
}
vis[gtn('F')] = 1;
dfs(cnt+1);
vis[gtn('F')] = 0;
for (ll j = 0; j < f::cnt; j++) {
g[x+f::gx[i][j]][y+f::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('G')]) {
for (ll i = 0; i < gg::num; i++) {
bool flag = 0;
for (ll j = 0; j < gg::cnt; j++) {
if (cant(x+gg::gx[i][j], y+gg::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < gg::cnt; j++) {
g[x+gg::gx[i][j]][y+gg::gy[i][j]] = gtn('G');
}
vis[gtn('G')] = 1;
dfs(cnt+1);
vis[gtn('G')] = 0;
for (ll j = 0; j < gg::cnt; j++) {
g[x+gg::gx[i][j]][y+gg::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('H')]) {
for (ll i = 0; i < h::num; i++) {
bool flag = 0;
for (ll j = 0; j < h::cnt; j++) {
if (cant(x+h::gx[i][j], y+h::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < h::cnt; j++) {
g[x+h::gx[i][j]][y+h::gy[i][j]] = gtn('H');
}
vis[gtn('H')] = 1;
dfs(cnt+1);
vis[gtn('H')] = 0;
for (ll j = 0; j < h::cnt; j++) {
g[x+h::gx[i][j]][y+h::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('I')]) {
for (ll i = 0; i < ii::num; i++) {
bool flag = 0;
for (ll j = 0; j < ii::cnt; j++) {
if (cant(x+ii::gx[i][j], y+ii::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < ii::cnt; j++) {
g[x+ii::gx[i][j]][y+ii::gy[i][j]] = gtn('I');
}
vis[gtn('I')] = 1;
dfs(cnt+1);
vis[gtn('I')] = 0;
for (ll j = 0; j < ii::cnt; j++) {
g[x+ii::gx[i][j]][y+ii::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('J')]) {
for (ll i = 0; i < jj::num; i++) {
bool flag = 0;
for (ll j = 0; j < jj::cnt; j++) {
if (cant(x+jj::gx[i][j], y+jj::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < jj::cnt; j++) {
g[x+jj::gx[i][j]][y+jj::gy[i][j]] = gtn('J');
}
vis[gtn('J')] = 1;
dfs(cnt+1);
vis[gtn('J')] = 0;
for (ll j = 0; j < jj::cnt; j++) {
g[x+jj::gx[i][j]][y+jj::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('K')]) {
for (ll i = 0; i < kk::num; i++) {
bool flag = 0;
for (ll j = 0; j < kk::cnt; j++) {
if (cant(x+kk::gx[i][j], y+kk::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < kk::cnt; j++) {
g[x+kk::gx[i][j]][y+kk::gy[i][j]] = gtn('K');
}
vis[gtn('K')] = 1;
dfs(cnt+1);
vis[gtn('K')] = 0;
for (ll j = 0; j < kk::cnt; j++) {
g[x+kk::gx[i][j]][y+kk::gy[i][j]] = 0;
}
}
}
}
if (!vis[gtn('L')]) {
for (ll i = 0; i < l::num; i++) {
bool flag = 0;
for (ll j = 0; j < l::cnt; j++) {
if (cant(x+l::gx[i][j], y+l::gy[i][j])) {
flag = 1;
break;
}
}
if (!flag) {
for (ll j = 0; j < l::cnt; j++) {
g[x+l::gx[i][j]][y+l::gy[i][j]] = gtn('L');
}
vis[gtn('L')] = 1;
dfs(cnt+1);
vis[gtn('L')] = 0;
for (ll j = 0; j < l::cnt; j++) {
g[x+l::gx[i][j]][y+l::gy[i][j]] = 0;
}
}
}
}
}
int main() {
//freopen("zhz.out", "w", stdout);
ll start = 1;
memset(g, -1, sizeof(g));
for (ll i = 1; i <= 10; i++) {
for (ll j = 1; j <= i; j++) {
char kk;
scanf("%c", &kk);
if (kk == '.') {
g[i][j] = 0;
} else {
if (!vis[gtn(kk)]) {
vis[gtn(kk)]++;
start++;
}
g[i][j] = gtn(kk);
}
}
cin.get();
}
dfs(start);
printf("No solution");
return 0;
}