请各位带佬帮忙看下,第一题用dfs遍历C数组里A数组所有可能出现的位置,这个代码咋错了?,顺便搞个得分投票:
#include <iostream> #include <vector> #include <map> #include <unordered_map> #include <queue> #include <set> #include <stack> #include <algorithm> #include <unordered_set> #include <cmath> using namespace std; #define max(a,b) (a)>(b)?(a):(b) #define min(a,b) (a)<(b)?(a):(b) int T, n, m, tmp; vector<int> a, b, c; vector<vector<int>> allp; vector<int> path; bool same(vector<int> a, vector<int> b) { if (a.size() != b.size()) return false; for (int i = 0; i < a.size(); ++i) { if (a[i] != b[i]) return false; } return true; } // 遍历C中A可能的位置 void dfs(int idx, int step) { if (step > n) return ; if (step == n) { allp.push_back(path); return ; } for (int i = idx+1; i < n+m; ++i) { if (c[i] == a[step]) { path.push_back(i); dfs(i, step+1); path.pop_back(); } } } int main() { cin>>T; while (T--) { cin>>n >> m; for (int i = 0; i < n; ++i) { cin>>tmp; a.push_back(tmp); } for (int j = 0; j < m; ++j) { cin>>tmp; b.push_back(tmp); } for (int k = 0; k < n+m; ++k) { cin>>tmp; c.push_back(tmp); } for (int i = 0; i < n+m; ++i) { if (c[i] == a[0]) { vector<int> newpath; path = newpath; path.push_back(i); dfs(i, 1); } } string ans = "not possible"; // 对于C数组所有可能的A的位置进行遍历 for (auto curp:allp) { vector<int> curb; vector<int> flag(n+m); for (auto i:curp) flag[i] = 1; for (int i = 0; i < n+m; ++i) { if (flag[i] == 0) curb.push_back(c[i]); } if (same(curb, b)) { ans = "possible"; break; } } cout<<ans<<endl; } return 0; }
全部评论
(14) 回帖