From 053639c181a036f60bd6c627520d5839b8db7689 Mon Sep 17 00:00:00 2001
From: Aditya Naik
Date: Mon, 14 May 2018 23:24:05 -0400
Subject: word: BFS not working due to cycles in graph

---
 429/word.cpp | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 429/word.in  | 22 +++++++++++++++++
 2 files changed, 99 insertions(+)
 create mode 100644 429/word.cpp
 create mode 100644 429/word.in

(limited to '429')

diff --git a/429/word.cpp b/429/word.cpp
new file mode 100644
index 0000000..83c727f
--- /dev/null
+++ b/429/word.cpp
@@ -0,0 +1,77 @@
+#include <iostream>
+#include <vector>
+#include <string>
+using namespace std;
+
+int get_dist(string a, string b);
+void make_graph(vector<string> wlist, int map[][200]);
+bool get_pathlen(int map[][200], vector<string> wlist, int start, int dest, string &path, bool visited[]);
+
+int main(){
+    int tc;
+    cin>>tc;
+    while(tc--){
+	string w="";
+	vector<string> wlist;
+	int map[200][200];
+	while(w!="*"){
+	    cin>>w;
+	    wlist.push_back(w);
+	}
+	make_graph(wlist, map);
+	
+	string s1, s2;
+	while(cin>>s1>>s2){
+	    int l1, l2;
+	    for(int i=0; i<wlist.size(); i++){
+		if(wlist[i]==s1)
+		    l1 = i;
+		else if(wlist[i]==s2)
+		    l2 = i;
+	    }
+	    int len = 0;
+	    bool visited[200];
+	    string path;
+	    get_pathlen(map, wlist, l1, l2, path, visited);
+	    cout<<s1<<" "<<s2<<" "<<path.length()-1<<endl;
+	}
+    }
+}
+
+bool get_pathlen(int map[][200], vector<string> wlist, int start, int dest, string &path, bool visited[]){
+    if(start==dest){
+	path+="a";
+	return true;
+   }
+    else{
+	visited[start]=true;
+	for(int j=0; j<26; j++){
+	    if(map[start][j]==1 && visited[j]==false){
+		visited[j]=true;
+		if(get_pathlen(map, wlist, j, dest, path, visited) == true){
+		    path+="a";
+		    return true;
+		}
+	    }
+	}
+	return false;
+    }
+}
+void make_graph(vector<string> wlist, int map[][200]){
+    for(int i=0; i<wlist.size(); i++)
+	for(int j=0; j<wlist.size(); j++)
+	    if(i!=j && get_dist(wlist[i], wlist[j])==1){
+		map[i][j] = 1;
+		map[j][i] = 1;
+	    }
+}
+
+int get_dist(string a, string b){
+    int dist = 0;
+    int len = a.length();    
+    if(len == b.length())
+	for(int i=0; i<len; i++)
+	    if(a[i]!=b[i])
+		dist++;
+    return dist;
+}
diff --git a/429/word.in b/429/word.in
new file mode 100644
index 0000000..b2a765d
--- /dev/null
+++ b/429/word.in
@@ -0,0 +1,22 @@
+1
+dip
+lip
+mad
+map
+maple
+may
+pad
+pip
+pod
+pop
+sap
+sip
+slice
+slick
+spice
+stick
+stock
+*
+spice stock
+may pod
+
-- 
cgit v1.2.3