社区讨论

求助为什么输入什么都是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 条回复,欢迎继续交流。

正在加载回复...