Homework Introduction

DFS

//填 5*5 的格子,每个格子4种可能
// 4^25 = 2^50 超时
//但是我们想合法的可能其实只有
// A.B.C 每一行ABC各有一个
// A(5,3) = 5*4*3 = 60, 每一行枚举的次数
// 60^5 的枚举次数,外加一点剪枝
//
//先暴力搜索A(n,3)种不同的行 60种
//依次填上每一行,check 俯视图/左视图,不行就剪枝

#include <bits/stdc++.h>
using namespace std;
int n;
string R, C;
bool flg;
string line[61];
int tot = 0;
// ans 记录已经填充好的部分
string ans[10];
bool used[3];

// e 是要填充的 点 的个数
// 枚举出第一行所有可能填充的序列
void dfs1(string now, int e) {
	if ((int)now.length() == n) {
		line[++tot] = now;  // 一行的可能性
		return;
	}
	for (int i = 0; i < 3; i++) {  // 枚举当前位置填充 ABC 中的一个
		if (!used[i]) {
			used[i] = 1;
			dfs1(now + char('A' + i), e);
			used[i] = 0;
		}
	}
	if (e)
		dfs1(now + '.', e - 1);
}

// 检查列是否符合要求
// 检查 从走往右看是否符合要求
// 检查从上往下看 是否符合要求
bool check(int d) {
	if (d == 0)
		return 1;
	// 判断是否和 R 匹配, 从左往右看
	for (int i = 0; i < d; i++) {  // 行
		for (int j = 0; j < n; j++) {
			if (ans[i][j] == '.')
				continue;
			if (ans[i][j] != R[i])  // 从左往右看不匹配
				return 0;
			else
				break;
		}
	}
	// 判断是否和 C 匹配 , 从上往下看
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < d; i++) {
			// 从上往下看,全是点, 不行
			if (i == n - 1 && ans[i][j] == '.')
				return 0;
			if (ans[i][j] == '.')
				continue;
			if (ans[i][j] != C[j])
				return 0;
			else
				break;
		}
	}
	// 判断列不能有重复的两个值
	// 之前我们的 dfs1 只保证了 行没有重复的,但是没有保证列没有重复的
	for (int j = 0; j < n; j++) {   // 列
		for (int i = 0; i < d; i++)   // 行
			for (int k = i + 1; k < d; k++)
				if (ans[i][j] != '.' && ans[i][j] == ans[k][j])
					return 0;
	}
	return 1;
}

void dfs2(int dep) {
	if (flg)
		return;
	// check  检查是否符合要求
	if (!check(dep))
		return;
	if (dep == n) {   // 证明填充满了,且符合要求
		flg = 1;
		cout << "Yes" << endl;
		for (int i = 0; i < n; i++)
			cout << ans[i] << endl;
		return;
	}
	// 枚举当前行可以填充哪些
	for (int i = 1; i <= tot; i++) {
		ans[dep] = line[i];
		dfs2(dep + 1);
	}
}

int main() {
	cin >> n >> R >> C;
	// n-3 要填充的点的个数
	dfs1("", n - 3);  // 枚举出来每一行所有可能的排列
	dfs2(0);
	if (!flg)
		cout << "No";
	return 0;
}
// 14 张牌
// 3+3+3+3+2
// 手上 13 张,枚举进来哪一张(注意不要绝张)
// cnt[3][9] 记录每种牌每一个点数有几张

// 枚举选的是 3 还是 2
// 3 顺子, 刻子(3张一样的)
// 顺子,枚举最小的一张(x,y)
// 用掉(x,y)(x,y+1)(x,y+2)

// 刻子, 枚举(x,y),用掉 (x,y)*3

// 依次枚举 2+3+3+3+3
// 如果最后用完, 说明加的这一张可以胡

#include <bits/stdc++.h>
using namespace std;
int cnt[3][10];
bool flg;
char a[20][3];
char res[100][3], k;
int m = 0;

// t 是花色, s 数字
void dfs(int t, int s) {
	if (t >= 3) {
		flg = 1;
		return;
	}
	// 花色 t  下的最后一张牌 
	if (s > 9) {  // 枚举下一个花色
		dfs(t + 1, 1);
		return;
	}
	if (cnt[t][s] == 0) {  // 当前没牌, 直接枚举下一张牌
		dfs(t, s + 1);
		return;
	}
	// 三个一样的牌
	if (cnt[t][s] == 3) {  // 三个一样的
		cnt[t][s] -= 3;
		dfs(t, s);
		cnt[t][s] += 3;
		if (flg)
			return;
	}
	// 三张连续的牌 
	if (s <= 7 && cnt[t][s] && cnt[t][s + 1] && cnt[t][s + 2]) {
		cnt[t][s]--, cnt[t][s + 1]--, cnt[t][s + 2]--;
		dfs(t, s);
		cnt[t][s]++, cnt[t][s + 1]++, cnt[t][s + 2]++;
		if (flg)
			return;
	}
}
bool check() {
	for (int t = 0; t < 3; t++)
		for (int n = 1; n <= 9; n++) {
			// tn 可以作为对子
			if (cnt[t][n] >= 2) {  // 先枚举对子
				cnt[t][n] -= 2;
				flg = 0;
				dfs(0, 1);   // 搜剩下的牌能否凑成 4 个 3
				cnt[t][n] += 2;  // 回溯
				if (flg)
					return 1;
			}}
	return 0;}
int main() {
	// 得到 13 张牌
	for (int i = 0; i < 13; i++)
		cin >> a[i];
	// 转换成对应的数字
	for (int i = 0; i < 13; i++) {
		int x = a[i][0] - '0';
		int t = a[i][1] == 's' ? 0 : a[i][1] == 'b' ? 1 : 2;
		cnt[t][x]++;  // 统计牌型个数
	}
	// 枚举所有的牌型
	for (int t = 0; t < 3; t++) {   // 枚举花色
		k = t == 0 ? 's' : t == 1 ? 'b' : 'c';
		for (int x = 1; x <= 9; x++) { // 枚举数字
			if (cnt[t][x] < 4) {
				cnt[t][x]++;  // 新来了一张 tx 的牌
				if (check()) {
					res[m][0] = x + '0';
					res[m][1] = k;
					res[m++][2] = '\0';
				}
				cnt[t][x]--;   // 回溯
			}}}
	if (m == 0) cout << "None";
	else	for (int i = 0; i < m; i++)
			cout << res[i] << " ";
	return 0;
}
Status
Done
Problem
19
Open Since
2026-2-24 0:00
Deadline
2026-3-31 23:59
Extension
24 hour(s)