D - ABC Puzzle
https://atcoder.jp/contests/abc326/tasks/abc326_d
Sample Input 1
Copy5 ABCBC ACAABSample Output 1
CopyYes AC..B .BA.C C.BA. BA.C. ..CBA
思路
充分利用约束条件,构造算法,
避免穷举所有情况,然后再根据约束条件判断情况的合法性。
如下代码,优点:思路清晰,效率高。
首先,例如row首字母条件, 枚举每行可能得排列结果
例如 row = ABCBC
row1 可能值为
ABC..
.ABC.
..ABC
ACB..
.ACB..
..ACB
同理可得其它行的可能选项。
使用dfs遍历行的组合
dfs(0) : 没有一行确定
->
dfs(1): 第一行确定
->
dfs(2): 前两行确定
...
dfs(5): 前五行确定, 进行条件满足性判定, 如果满足,打印结果退出, 如果没有,则向上回溯, 继续遍历第五行的其它可选项。
Code
https://atcoder.jp/contests/abc326/submissions/47367840
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; bool cntCol(vector<string>& grid) { int n = grid.size(); for(int j = 0; j < n; j++) { vector<int> cnt(3); for(int i = 0; i < n; i++) { ++cnt[grid[i][j] - 'A']; } if (cnt[0] != 1 || cnt[1] != 1 || cnt[2] != 1) return false; } return true; } bool dfs(vector<vector<string>>& configures, vector<string>& grid, string& row, string& col, int idx, vector<bool>& seen) { if (idx == row.size()) { if (cntCol(grid)) { cout << "Yes" << endl; for(string& val : grid) cout << val << endl; return true; } return false; } for(string& s : configures[row[idx] - 'A']) { bool flag = true; vector<bool> nxt = seen; for(int j = 0; j < col.size(); j++) { if (!nxt[j] && s[j] != '.') { if (s[j] == col[j]) nxt[j] = true; else { flag = false; break; } } } if (!flag) continue; grid.push_back(s); if (dfs(configures, grid, row, col, idx + 1, nxt)) return true; grid.pop_back(); } return false; } void task() { int n; cin >> n; string r, c; cin >> r >> c; string s = "ABC"; while(s.size() < n) s.push_back('.'); sort(s.begin(), s.end()); vector<vector<string>> configures(3); vector<bool> seen(n, false); vector<string> grid; do { for(char c : s) { if (c != '.') { configures[c - 'A'].push_back(s); break; } } } while(next_permutation(s.begin(), s.end())); if(!dfs(configures, grid, r, c, 0, seen)) cout << "No" << endl; } int main() { task(); return 0; }
标签:ATCODER,ABC,..,--,dfs,int,vector,grid From: https://www.cnblogs.com/lightsong/p/17818353.html