校园二手交易网站开发背景,国外网站dns,wordpress批量修改字体,网站建设和管理情况看了很多题解都是写了一大坨#xff0c;看起来非常的混乱#xff0c;然而自己去写的时候又不可避免的写了一坨#xff0c;只能尽可能的去优化代码可读性。 Time Limit: 4 sec / Memory Limit: 1024 MB
问题陈述
给你一个整数 N N N 和长度为 N N N 的字符串 R R R 和 …看了很多题解都是写了一大坨看起来非常的混乱然而自己去写的时候又不可避免的写了一坨只能尽可能的去优化代码可读性。 Time Limit: 4 sec / Memory Limit: 1024 MB
问题陈述
给你一个整数 N N N 和长度为 N N N 的字符串 R R R 和 C C C 它们由 A 、 B A、B A、B 和 C C C 组成。请解决下面的问题。
有一个 N × N N×N N×N 网格。所有单元格最初都是空的。您最多可以在每个单元格中写入 A 、 B A、B A、B 和 C C C 中的一个字符。(也可以让单元格为空。
确定是否有可能满足以下所有条件如果有可能请打印一种满足这些条件的方法。
每一行和每一列正好包含一个 A、一个 B和一个 C。写入 i − t h i-th i−th 行中最左边的字符与 R R R 中的 i − t h i-th i−th 字符相匹配。写在 i − t h i -th i−th 列中最顶端的字符与 C C C 的 i − t h i -th i−th 字符匹配。
限制因素 N N N 是介于 3 3 3 和 5 5 5 之间的整数包括首尾两个整数。 R R R 和 C C C 是长度为 N N N 的字符串由 A、B和 C组成。
输入
输入内容由标准输入法提供格式如下
N
R
C输出
如果无法填充网格以满足问题陈述中的条件则单行打印 “No”。 否则按以下格式打印一种填充网格的方法
Yes
A1
A2
⋮
AN第一行应包含 “是”。随后 N N N 行中的 i − t h i-th i−th 应包含长度为 N N N 的字符串 A i A_i Ai 。
如果 A i A_i Ai 的第 j j j 字符是 “.”则表示从上往下 i − t h i-th i−th 行和从左往右 j − t h j-th j−th 列中的单元格为空。如果 A i A_i Ai 的第 j j j 个字符是 “A”那么它表示 A 写在从上往下第 i i i 行、从左往上第 j j j 列的单元格中。如果 A i A_i Ai 的第 j j j 个字符是 “B”那么它表示 B 被写在从上往下第 i i i 行、从左往上第 j j j 列的单元格中。如果 A i A_i Ai 的第 j j j 个字符是 “C”那么它表示 C 被写在从上往下第 i i i 行、从左往上第 j j j 列的单元格中。
如果有多种正确的填充网格的方法您可以打印其中任何一种。
Sample Input 1
5
ABCBC
ACAABSample Output 1
Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA对于这题4s的时间限制并且联想到之前做过的八皇后问题就想到可以用DFS来解决。
题目要求每行每列都只能有各一个 A , B , C A,B,C A,B,C 且都必须有这三个字母我们可以以答案数组的层数同时作为dfs的层数然后在搜到每一层的时候把这一层应有的 A , B , C A,B,C A,B,C 三个字母全部填上这样我们就保证了每一行有且仅有一对 A , B , C A,B,C A,B,C。 所以我们仅仅需要再判断一下每一列是否满足要求即可。 在这里就可以转化为八皇后模型了开三个判断列的数组每个对应一个字母如果可以填就填上。
对于如何在一层里填上三个字母我们需要一次性填上三个。 假如你写出了三层循环来找字母那么你填出来之后就变成了一行只有一个字母了。 所以写出一个三层循环每一层循环的是每个字母要填的位置这里把重叠的位置全部continue掉。
代码
#includeiostream
#includecstring
#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); //直接从这里终结整个程序}
//--------------------------------------------------------------------------------------//搜索部分//这里枚举的ijk是字母ABC填入的位置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和CB和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;
}
