给定两个字符串,记为start和to,再给定一个字符串列表list,list中一定包含to,list中没有重复的字符串。所有的字符串都是小写的。规定start每次只能改变一个字符,最终的目标是彻底变成to,但是每次变成新字符串必须在list中存在。请返回所有的最短的变换路径(按照字典序最小的顺序输出)。
输出包含多行,第一行包含一个整数n,代表list的中字符串的个数,第二行中包含两个字符串,分别代表start和to。接下来n行,每行一个字符串,代表lis[i](保证字符串长度都为3)。
如果存在转换的路径,请先输出“YES”,然后按照字典序最小的顺序输出所有路径。如果不存在请输出“NO”。
8 abc cab cab acc cbc ccc cac cbb aab abb
YES abc -> abb -> aab -> cab abc -> abb -> cbb -> cab abc -> cbc -> cac -> cab abc -> cbc -> cbb -> cab
import java.util.*; public class Main { public static HashMap<String, TreeSet<String>> graph = new HashMap<>(); public static ArrayList<String> nodes = new ArrayList<>(); public static HashMap<String, TreeSet<String>> pre = new HashMap<>(); public static ArrayList<ArrayList<String>> res = new ArrayList<>(); public static HashMap<String, Integer> distance = new HashMap<>(); public static class Pair { public String id; public Integer distance; public Pair(String id, Integer distance) { this.id = id; this.distance = distance; } } public static Comparator<Pair> disComparator = new Comparator<Pair>() { @Override public int compare(Pair o1, Pair o2) { return o1.distance-o2.distance; } }; public static Comparator<String> charComparator = new Comparator<String>() { @Override public int compare(String o1, String o2) { return o1.compareTo(o2); } }; public static Comparator<ArrayList<String>> listComparator = new Comparator<ArrayList<String>>() { @Override public int compare(ArrayList<String> o1, ArrayList<String> o2) { return o1.toString().compareTo(o2.toString()); } }; public static boolean isAdjoin(String a, String b) { if (a.length() != b.length()) return false; int differentCharCnt = 0; for (int i = 0; i < a.length(); i++) { if (a.charAt(i) != b.charAt(i)) { differentCharCnt++; } } return differentCharCnt == 1; } public static boolean isExistPath(String start, String to) { PriorityQueue<Pair> queue = new PriorityQueue<>(disComparator); queue.offer(new Pair(start, 0)); distance.put(start, 0); HashSet<String> visited = new HashSet<>(); while (!queue.isEmpty()) { Pair cur = queue.poll(); if (visited.contains(cur.id)) continue; visited.add(cur.id); for (String next : graph.get(cur.id)) { if (!visited.contains(next)) { if (distance.get(cur.id) + 1 < distance.get(next)) { distance.put(next, distance.get(cur.id)+1); pre.put(next, new TreeSet<>(charComparator)); pre.get(next).add(cur.id); } else if (distance.get(cur.id) + 1 == distance.get(next)) { pre.get(next).add(cur.id); } queue.offer(new Pair(next, distance.get(next))); } } } return distance.get(to) != Integer.MAX_VALUE; } public static void getMinPath(String start, String to, ArrayList<String> solution) { if (to.equals(start)) { solution.add(start); ArrayList<String> temp = new ArrayList<>(); for (int i = solution.size()-1; i >= 0; i--) { temp.add(solution.get(i)); } solution.remove(start); res.add(temp); return; } solution.add(to); for (String preNode : pre.get(to)) { getMinPath(start, preNode, solution); } solution.remove(to); } public static void main(String[] args) { Scanner input = new Scanner(System.in); int N = input.nextInt(); String start = input.next(); String to = input.next(); for (int i = 0; i < N; i++) { nodes.add(input.next()); } nodes.add(start); // initialize for (String node : nodes) { graph.put(node, new TreeSet<>(charComparator)); distance.put(node, Integer.MAX_VALUE); } // construct graph for (int i = 0; i < nodes.size(); i++) { for (int j = 0; j < nodes.size(); j++) { if (isAdjoin(nodes.get(i), nodes.get(j))) { graph.get(nodes.get(i)).add(nodes.get(j)); } } } if (isExistPath(start, to)) { System.out.println("YES"); getMinPath(start, to, new ArrayList<>()); res.sort(listComparator); for (ArrayList<String> path : res) { for (int i = 0; i < path.size(); i++) { System.out.print(path.get(i)); if (i != path.size()-1) { System.out.print(" -> "); } } System.out.println(); } } else { System.out.println("NO"); } } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void getShortPaths(String cur, String to, Map<String, List<String>> nexts, Map<String, Integer> distances, Deque<String> path, List<List<String>> res) { path.add(cur); if (cur.equals(to)) { res.add(new ArrayList<>(path)); path.pollLast(); return; } for (String next : nexts.get(cur)) { if (distances.get(next) == distances.get(cur) + 1) { getShortPaths(next, to, nexts, distances, path, res); } } path.pollLast(); } public static Map<String, Integer> getDistance(String from, Map<String, List<String>> nexts) { Map<String, Integer> distances = new HashMap<>(); Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); distances.put(from, 0); queue.offer(from); visited.add(from); while (!queue.isEmpty()) { String cur = queue.poll(); for (String s : nexts.get(cur)) { if (!visited.contains(s)) { distances.put(s, distances.get(cur) + 1); queue.offer(s); visited.add(s); } } } return distances; } public static Map<String, List<String>> getNexts(List<String> words) { Map<String, List<String>> nexts = new HashMap<>(); Set<String> wordSet = new HashSet<>(words); for (String s : words) { nexts.put(s, new ArrayList<>()); } for (String s : words) { nexts.put(s, getNext(s, wordSet)); } return nexts; } private static List<String> getNext(String word, Set<String> wordSet) { List<String> res = new ArrayList<>(); char[] chs = word.toCharArray(); for (char c = 'a'; c <= 'z'; c++) { for (int i = 0; i < word.length(); i++) { if (c != chs[i]) { char t = chs[i]; chs[i] = c; if (wordSet.contains(String.valueOf(chs))) { res.add(String.valueOf(chs)); } chs[i] = t; } } } return res; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] line = br.readLine().split(" "); String from = line[0]; String to = line[1]; List<String> words = new ArrayList<>(); words.add(from); for (int i = 0; i < n; i++) { words.add(br.readLine()); } Map<String, List<String>> nexts = getNexts(words); Map<String, Integer> distance = getDistance(from, nexts); Deque<String> path = new LinkedList<>(); List<List<String>> res = new ArrayList<>(); getShortPaths(from, to, nexts, distance, path, res); if (res.size() == 0) { System.out.println("NO"); return; } System.out.println("YES"); List<String> paths = new ArrayList<>(); for (List<String> strs : res) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < strs.size(); i++) { sb.append(strs.get(i)); if (i != strs.size() - 1) { sb.append(" -> "); } } paths.add(sb.toString()); } Collections.sort(paths); for (String p : paths) { System.out.println(p); } } }
#include<bits/stdc++.h> using namespace std; vector<string> getNext(string word, const unordered_set<string>& dict){ vector<string> ret; for(char cur = 'a'; cur <= 'z'; ++cur){ for(int i = 0; i<word.size(); ++i){ if(word[i] != cur){ char tmp = word[i]; word[i] = cur; if(dict.count(word)){ ret.push_back(word); } word[i] = tmp; } } } return ret; } unordered_map<string,vector<string>> getNexts(vector<string>& words){ unordered_set<string> dict(words.begin(), words.end()); unordered_map<string, vector<string>> nexts; for(int i = 0; i<words.size(); ++i){ nexts[words[i]] = getNext(words[i], dict); } return nexts; } unordered_map<string, int> getDistances(string start, const unordered_map<string,vector<string>>& nexts){ unordered_map<string, int> distances; distances[start] = 0; queue<string> que; que.push(start); unordered_set<string> s; s.insert(start); while(!que.empty()){ string cur = que.front(); que.pop(); for( string str:nexts.at(cur)){ if(s.count(str)==0){ distances[str] = distances[cur]+1; que.push(str); s.insert(str); } } } return distances; } void getShortestPaths(string cur, string to, const unordered_map<string, vector<string>>& nexts, const unordered_map<string,int>& distances, vector<string> solution, vector<vector<string>>& res){ solution.push_back(cur); if(to.compare(cur)==0){ res.push_back(solution); }else{ for(string next:nexts.at(cur)){ if(distances.at(next)==distances.at(cur)+1){ getShortestPaths(next, to, nexts, distances, solution, res); } } } } vector<vector<string>> findMinPaths(string start, string to, vector<string> list){ //把start加入list list.push_back(start); //根据list生成每一个字符串nexts信息 unordered_map<string,vector<string>> nexts = getNexts(list); //从start字符串出发,利用nexts信息和宽度优先遍历的方式,求出每一个字符串到start的最短距离 unordered_map<string, int> distances = getDistances(start, nexts); vector<string> pathList; vector<vector<string>> res; //收集路径 getShortestPaths(start, to, nexts, distances, pathList, res); return res; } void myPrint(vector<string>& v){ for(int i = 0; i<v.size(); ++i){ if(i!=0){ cout<<" -> "; } cout<<v[i]; } cout<<endl; } int main(){ int n; cin>>n; string start, to; cin>>start>>to; vector<string> list(n); for(int i = 0; i<n; ++i){ list[i].resize(3); scanf("%s", &list[i][0]); } vector<vector<string>> ret = findMinPaths(start, to, list); sort(ret.begin(), ret.end()); if(ret.size()>0){ cout<<"YES"<<endl; for(vector<string> it:ret){ myPrint(it); } }else{ cout<<"NO"<<endl; } return 0; }
#include <iostream> #include <string> #include <unordered_set> #include <unordered_map> #include <queue> #include <vector> #include <set> using namespace std; void bfs( unordered_map<string, vector<string>> &edges, unordered_map<string, int> &dis, string &start){ queue<string> q; unordered_set<string> se; q.push(start); se.insert(start); dis[start] = 0; while (!q.empty()){ string s = q.front(); q.pop(); for (string next : edges[s]){ if (!se.count(next)){ q.push(next); se.insert(next); dis[next] = dis[s] + 1; } } } } void bfs(unordered_map<string, vector<string>> &edges, unordered_map<string, int> &dis, string &start, string &to, queue<string> &help, set<string> &ans){ queue<string> q; q.push(start); help.push(start); while(!q.empty()){ string s = q.front(); q.pop(); if(s == to){ ans.insert(help.front()); help.pop(); }else{ for (string next : edges[s]){ if (dis[next] == dis[s] + 1){ q.push(next); help.push(help.front() + " -> " + next); } } help.pop(); } } } int main(){ int n; cin>>n; string start, to; cin>>start>>to; //构图 //1.set表示点集,构造点集 unordered_set<string> sets; sets.insert(start); while(n--){ string s; cin>>s; sets.insert(s); } //2.构造边集 unordered_map<string, vector<string>> edges; for (string s : sets){ vector<string> v; for (int i = 0; i < 3; ++i){ for (int j = 'a'; j <= 'z'; ++j){ string t = s; t[i] = j; if (s != t && sets.count(t)){ v.push_back(t); } } } edges[s] = v; } //3.先利用bfs生成start到各个点的最短距离 unordered_map<string, int> dis; bfs(edges, dis, start); //4.再利用bfs生成路径(其实用bfs可以直接求出来,只不过会多些无所谓的搜索, //导致内存爆了,我直接bfs到第12个用例爆内存了) set<string> ans; queue<string> q; bfs(edges, dis, start, to, q, ans); if (!ans.empty()){ cout<<"YES"<<endl; for (string s : ans){ cout<<s<<endl; } }else{ cout<<"NO"<<endl; } return 0; }
// 建图 + bfs求最短路 + dfs求相应的路径 + 排序输出字典序最小的路径 #include<iostream> #include<vector> #include<algorithm> #include<queue> #include<cstring> using namespace std; vector<int> h, e, ne; vector<string> arr; vector<vector<int>> ans; int idx = 0; void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx++; } vector<bool> st; void dfs(vector<int> &res, int idx, int cur_dis, int min_distance, int e_idx){ if(cur_dis > min_distance) { if(idx == e_idx){ ans.push_back(res); } return; } for(int i = h[idx];~i;i = ne[i]){ int j = e[i]; if(!st[j]){ st[j] = true; res.push_back(j); dfs(res, j, cur_dis + 1, min_distance, e_idx); res.pop_back(); st[j] = false; } } } int main(){ int n; cin>>n; string start ,end; cin>>start>>end; int e_index = -1; e.resize(n*n, 0); h.resize(n+1, -1); ne.resize(n*n, 0); st.resize(n+10, false); int s_index; for(int i = 0;i<n;i++) { string s; cin>>s; arr.push_back(s); } if(find(arr.begin(), arr.end(), start) != arr.end()) { cout<<"YES"<<endl; cout<<start<<endl; return 0; } arr.push_back(start); n++; sort(arr.begin(), arr.end()); for(int i = 0;i<n;i++) { if(arr[i] == start) s_index = i; else if(arr[i] == end) e_index = i; } for(int i = 0;i<n;i++) for(int j = i+1;j<n;j++){ int cnt = 0; for(int k = 0;k<arr[i].size();k++){ if(arr[i][k] != arr[j][k]) cnt++; } if(cnt == 1) add(i, j), add(j, i); } queue<int> q; vector<int> dis(n+1, 0); q.push(s_index); int min_distance = 0; while(!q.empty()){ auto cur = q.front(); q.pop(); for(int i = h[cur];~i;i = ne[i]){ int j = e[i]; if(dis[j] == 0){ q.push(j); dis[j] = dis[cur] + 1; if(j == e_index){ min_distance = dis[j]; break; } } } } // cout<<s_index<<" "<<e_index<<" "<<min_distance<<endl; if(min_distance>0){ cout<<"YES"<<endl; vector<int> v; v.push_back(s_index); // 用min_distance dfs dfs(v, s_index, 1,min_distance, e_index); sort(ans.begin(), ans.end()); // cout<<arr[ans[0][ans[0].size()-1]]<<endl; for(int i = 0;i<ans.size();i++){ for(int j = 0;j<ans[i].size()-1;j++) cout<<arr[ans[i][j]]<<" -> "; cout<<arr[ans[i][ans[i].size()-1]]<<endl; } }else{ cout<<"NO"<<endl; } return 0; }
#include<cstdio> #include<vector> #include<iostream> #include<unordered_map> #include<string> #include<climits> #include<algorithm> using namespace std; int n; string s, d; vector<vector<string> > ans; vector<string> temp; int minstep = INT_MAX; unordered_map<string, int> m, m1; int cmp(vector<string> v1, vector<string> v2) { for (int i = 0; i < v1.size(); ++i) { if (v1[i] != v2[i]) return v1[i] < v2[i]; } } void dfs(string ss, int step) { if (step > minstep) return; temp.push_back(ss); if (ss == d) { if (step < minstep) { minstep = step; ans.clear(); ans.push_back(temp); } else if (step == minstep) { ans.push_back(temp); } temp.pop_back(); return; } for (int i = ss.size()-1; i >= 0; --i) { for (int j = 25; j >= 0; --j) { char tmp = ss[i]; ss[i] = j + 'a'; if (m[ss] == 0 && m1[ss] == 1) { m[ss] = 1; dfs(ss, step + 1); m[ss] = 0; } ss[i] = tmp; } } temp.pop_back(); } int main() { string q; while (scanf("%d", &n) != EOF) { m.clear(); m1.clear(); ans.clear(); temp.clear(); minstep = INT_MAX; cin >> s >> d; for (int i = 0; i < n; ++i) { cin >> q; m1[q] = 1; } dfs(s, 0); if (ans.size() == 0) printf("NO\n"); else { printf("YES\n"); sort(ans.begin(), ans.end(), cmp); for (int i = 0; i < ans.size(); ++i) { for (int j = 0; j < ans[i].size(); ++j) { if (j == 0) cout << ans[i][j]; else cout << " -> " << ans[i][j]; } cout << endl; } } } return 0; }