AtCoder - ABC 326 - D - ABC Puzzle （DFS）

本文主要是介绍AtCoder - ABC 326 - D - ABC Puzzle （DFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

看了很多题解都是写了一大坨，看起来非常的混乱，然而自己去写的时候又不可避免的写了一坨，只能尽可能的去优化代码可读性。

Time Limit: 4 sec / Memory Limit: 1024 MB

问题陈述

给你一个整数 $N$ 和长度为 $N$ 的字符串 $R$ 和 $C$ ，它们由 $A 、 B$ 和 $C$ 组成。请解决下面的问题。

有一个 $N \times N$ 网格。所有单元格最初都是空的。您最多可以在每个单元格中写入 $A 、 B$ 和 $C$ 中的一个字符。(也可以让单元格为空）。

确定是否有可能满足以下所有条件，如果有可能，请打印一种满足这些条件的方法。

每一行和每一列正好包含一个 A、一个 B和一个 C。写入 $i - t h$ 行中最左边的字符与 $R$ 中的 $i - t h$ 字符相匹配。写在 $i - t h$ 列中最顶端的字符与 $C$ 的 $i - t h$ 字符匹配。

限制因素

$N$ 是介于 $3$ 和 $5$ 之间的整数，包括首尾两个整数。 $R$ 和 $C$ 是长度为 $N$ 的字符串，由 A、B和 C组成。

输入

输入内容由标准输入法提供，格式如下

N
R
C

输出

如果无法填充网格以满足问题陈述中的条件，则单行打印 “No”。
否则，按以下格式打印一种填充网格的方法：

Yes
A1
A2 
⋮
AN

第一行应包含 “是”。随后 $N$ 行中的 $i - t h$ 应包含长度为 $N$ 的字符串 $A_i$ 。

如果 $A_i$ 的第 $j$ 字符是 “.”，则表示从上往下 $i - t h$ 行和从左往右 $j - t h$ 列中的单元格为空。
如果 $A_i$ 的第 $j$ 个字符是 “A”，那么它表示 "A " 写在从上往下第 $i$ 行、从左往上第 $j$ 列的单元格中。
如果 $A_i$ 的第 $j$ 个字符是 “B”，那么它表示 "B "被写在从上往下第 $i$ 行、从左往上第 $j$ 列的单元格中。
如果 $A_i$ 的第 $j$ 个字符是 “C”，那么它表示 "C "被写在从上往下第 $i$ 行、从左往上第 $j$ 列的单元格中。

如果有多种正确的填充网格的方法，您可以打印其中任何一种。

Sample Input 1

5
ABCBC
ACAAB

Sample Output 1

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

对于这题4s的时间限制，并且联想到之前做过的八皇后问题，就想到可以用DFS来解决。

题目要求每行每列都只能有各一个 $A, B, C$ 且都必须有这三个字母，我们可以以答案数组的层数同时作为dfs的层数，然后在搜到每一层的时候把这一层应有的 $A, B, C$ 三个字母全部填上，这样我们就保证了每一行有且仅有一对 $A, B, C$ 。 所以我们仅仅需要再判断一下每一列是否满足要求即可。
在这里就可以转化为八皇后模型了，开三个判断列的数组，每个对应一个字母，如果可以填就填上。

对于如何在一层里填上三个字母，我们需要一次性填上三个。
假如你写出了三层循环来找字母，那么你填出来之后就变成了一行只有一个字母了。
所以写出一个三层循环，每一层循环的是每个字母要填的位置，这里把重叠的位置全部continue掉。

代码：

#include<iostream>
#include<cstring>
#pragma warning(disable: 4996)
using namespace std;
const int N = 10;int n;char g[N][N];	//答案数组
char a[N];
char b[N];//判断某一列是否已经有A或B或C
bool a_line[N];
bool b_line[N];
bool c_line[N];//u代表的是层数，即答案数组的x轴
void dfs(int u) {if (u == n + 1) {	//如果搜满了所有层，就进行判断for (int i = 1; i <= n; i++) {		//第一次判断for (int j = 1; j <= n; j++) {	//判断最左边的字母是不是符合字符串A的顺序if (g[i][j] != '.') {if (g[i][j] == a[i])break;else return;}if (j == n && g[i][j] == '.')return;	//要是搜完了所有的甚至都没一个字母，直接跳}}for (int i = 1; i <= n; i++) {		//第二次判断for (int j = 1; j <= n; j++) {	//判断最上边的字母是不是符合字符串B的顺序if (g[j][i] != '.') {		//以下同理if (g[j][i] != b[i])return;else break;}if (j == n && g[j][i] == '.')return;}}
//-------------------------------------------------------------------------------------//输出答案cout << "Yes" << endl;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cout << g[i][j];}puts("");}exit(0);	//直接从这里终结整个程序}
//--------------------------------------------------------------------------------------//搜索部分//这里枚举的i，j，k是字母A，B，C填入的位置for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j)continue;	//A和B不能填到一个位置，直接continuefor (int k = 1; k <= n; k++) {if (i == k || j == k)continue;	//A和C，B和C不能填到一个位置if (!a_line[i] && !b_line[j] && !c_line[k]){//如果这一列还没有被填入过相应的字母g[u][i] = 'A', g[u][j] = 'B', g[u][k] = 'C';a_line[i] = b_line[j] = c_line[k] = 1;dfs(u + 1);//搜下一层//回溯状态g[u][i] = g[u][j] = g[u][k] = '.';a_line[i] = b_line[j] = c_line[k] = 0;}}}}
}
//----------------------------------------------------------------------------------------------
int main() {cin >> n;scanf("%s%s", a + 1, b + 1);for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {g[i][j] = '.';}}dfs(1);//如果没找到答案就直接输出Nocout << "No";return 0;
}