社区讨论
求助为什么输入什么都是no solution(s)
UVA211 多米诺效应 The Domino Effect参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lo3g5t7u
- 此快照首次捕获于
- 2023/10/24 06:06 2 年前
- 此快照最后确认于
- 2023/10/24 06:06 2 年前
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#define debug { cout << "debug" << endl; }
#define debug2 { }
using namespace std;
int matrix[10][10], ans[10][10];
int movx[]={0, 1};
int movy[]={1, 0};
int domino[10][10], vis[10][10], vis2[10][10];
int data=0, ansc=0, tmpflag=0;
bool read() {
if(scanf("%d", &matrix[1][1])==1) {
for(int i=1;i<=7; i++) {
for(int j=1; j<=8; j++) {
if(i==1 && j==1) continue;
scanf("%d", &matrix[i][j]);
}
}
return true;
}
return false;
}
void outputans() {
for(int i=1; i<=7; i++) {
for(int j=1; j<=8; j++) {
printf("%d%c", ans[i][j], ((j==8)?'\n':' '));
}
}
}
inline bool check(int x, int y) {
return x>=1 && x<=7 && y>=1 && y<=8 && !vis2[x][y];
}
void dfs(int x, int y, int last, int lx, int ly) {
if(tmpflag==28) {
tmpflag=0;
int amx=min(last, matrix[x][y]), bmx=max(last, matrix[x][y]);
if(!vis[amx][bmx]) {
ansc++;
ans[x][y]=ans[lx][ly]=domino[amx][bmx];
outputans();
}
}
if(last!=-1) {
for(int i=0; i<2; i++) {
int nx=x+movx[i], ny=y+movy[i];
if(!check(nx, ny)) return;
int amx=min(last, matrix[x][y]), bmx=max(last, matrix[x][y]);
if(!vis[amx][bmx]) {
ans[x][y]=ans[lx][ly]=domino[amx][bmx];
vis[amx][bmx]=1; vis2[nx][ny]=1; tmpflag++;
dfs(nx, ny, -1, -1, -1);
vis[amx][bmx]=0; vis2[nx][ny]=0; tmpflag--;
}
}
}else{
for(int i=0; i<2; i++) {
int nx=x+movx[i], ny=y+movy[i];
if(!check(nx, ny)) return;
vis2[nx][ny]=1;
dfs(nx, ny, matrix[x][y], x, y);
vis2[nx][ny]=0;
}
}
}
signed main() {
int cnt=0;
for(int i=0; i<=6; i++) {
for(int j=i; j<=6; j++) {
domino[i][j]=(++cnt);
}
}
while(read()) {
ansc=0;
memset(vis, 0, sizeof(vis));
memset(vis2, 0, sizeof(vis2));
printf("Layout #%d:\n", ++data);
for(int i=1; i<=7; i++) {
for(int j=1; j<=8; j++) {
printf("%d%c", matrix[i][j], ((j==8)?'\n':' '));
}
}
printf("Maps resulting from layout #1 are:\n");
vis2[1][1]=1;
dfs(1, 1, -1, -1, -1);
printf("There are %d solution(s) for layout #%d.\n", ansc, data);
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...