top of page

2019 CCC J5 c++ solution

#include <iostream> #include <vector> #include <stack> #include <queue> #include <set> using namespace std; //index 0 ===>rule string rule_source[3]; string rule_dst[3]; int steps; string start; string dest; set<string> hist[16]; bool dfs(string s, int n , vector<int> r, vector<int> p, vector<string> w){ if(n >= steps){ return false; } for(int i = 0 ; i < 3; i++){ string cur = s; for (int j = 0; j < s.size(); j++){ if(cur[j] == rule_source[i][0] && j + rule_source[i].size() <= cur.size() && cur.substr(j, rule_source[i].size()) == rule_source[i]){ string dst = cur.substr(0, j) + rule_dst[i] + cur.substr(j + rule_source[i].size()); if(hist[n+1].find(dst) == hist[n+1].end()){ r.push_back(i+1); p.push_back(j+1); w.push_back(dst); if(n+1 == steps){ if(dst == dest){ for(int k = 0; k < steps;k++){ cout<<r[k]<<" "<<p[k]<<" "<<w[k]<<endl; } return true; } else{ r.pop_back(); p.pop_back(); w.pop_back(); } } else{ hist[n+1].insert(dst); if(dfs(dst, n+1, r, p, w) == true){ return true; } else{ r.pop_back(); p.pop_back(); w.pop_back(); } } } } } } return false; } int main() { for(int i = 0; i < 3; i++){ cin >> rule_source[i]; cin >> rule_dst[i]; } cin >> steps; cin >> start; cin >> dest; vector<int> R; vector<int> P; vector<string> W; hist[0].insert(start); dfs(start, 0, R, P, W); return 0; }

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

Commenti


bottom of page