diff options
| -rw-r--r-- | 429/in | 72 | ||||
| -rw-r--r-- | 429/in2 | 7 | ||||
| -rw-r--r-- | 429/word.c | 25 | ||||
| -rw-r--r-- | 429/word.cpp | 52 | ||||
| -rw-r--r-- | 429/word.in | 67 | ||||
| -rw-r--r-- | log.org | 11 |
6 files changed, 50 insertions, 184 deletions
@@ -1,67 +1,13 @@ -4 +2 -dip -lip -mad -map -maple -may -pad -pip -pod -pop -sap -sip -slice -slick -spice -stick -stock +aa +bb +ac * -spice stock -may pod +aa ac -dip -lip -mad -map -mapl -maple -may -pad -pip -pod -pop -sap -sip -slice -slick -spice -stick -stock +aa +ab +bb * -spice slick -may mad -map maple -maple map -map map - -mapl -maple -mba -mbal -mbale -mbple -* -mba mapl - -map -mapl -maple -mba -mbal -mbale -mbp -mbple -* -mba mapl +aa bb diff --git a/429/in2 b/429/in2 deleted file mode 100644 index 8adc3ce..0000000 --- a/429/in2 +++ /dev/null @@ -1,7 +0,0 @@ -1 - -pip -slkdj -sdwi -sdkj -*
\ No newline at end of file diff --git a/429/word.c b/429/word.c deleted file mode 100644 index f8363aa..0000000 --- a/429/word.c +++ /dev/null @@ -1,25 +0,0 @@ -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -int main(){ - int tc; - char *word = malloc(10); - size_t st = 10; - scanf("%d", &tc); - while(tc--){ - getline(&word, &st, stdin); /* blank line after tc number */ - char dict[200][10]; - int i = 0; - - getline(&word, &st, stdin); - while(word[0]!='*'){ - memcpy(dict[i++], word, st); - getline(&word, &st, stdin); - } - int j=0; - for(;j<i; j++){ - printf("%s", dict[j]); - } - } -} diff --git a/429/word.cpp b/429/word.cpp index 6685b17..066b59c 100644 --- a/429/word.cpp +++ b/429/word.cpp @@ -5,8 +5,8 @@ #include <sstream> using namespace std; -int get_dist(string a, string b); -void make_graph(vector<string> wlist, int map[][200]); +void makeGraph(vector<string> wlist, int map[][200]); +int getDist(string a, string b); int bfs(int map[][200], int start, int dest, int s); int main(){ @@ -15,31 +15,36 @@ int main(){ while(tc--){ string w=""; vector<string> wlist; - int map[200][200]; + int map[200][200] = {0}; + cin>>w; while(w!="*"){ - cin>>w; wlist.push_back(w); + cin>>w; } - make_graph(wlist, map); + makeGraph(wlist, map); cin.ignore(); string line, s1, s2; getline(cin, line); while(line!=""){ - int l1, l2; + int l1, l2; /* indices to words in map */ istringstream iss(line); iss>>s1>>s2; for(int i=0; i<wlist.size(); i++){ if(wlist[i]==s1) l1 = i; - else if(wlist[i]==s2) + if(wlist[i]==s2) l2 = i; } - - cout<<s1<<" "<<s2<<" "<<bfs(map, l1, l2, wlist.size())<<"\n"; + int dist; + + dist = bfs(map, l1, l2, wlist.size()); + cout<<s1<<" "<<s2<<" "<<dist<<"\n"; getline(cin, line); } + if(tc>0) + cout<<endl; } } @@ -58,7 +63,7 @@ while !q.empty int bfs(int map[][200], int start, int dest, int s){ queue<int> q; int pred[200], n; - bool visited[200] = {false}; + bool visited[200] = {false}; q.push(start); while(!q.empty()){ @@ -81,21 +86,32 @@ int bfs(int map[][200], int start, int dest, int s){ return len; } -void make_graph(vector<string> wlist, int map[][200]){ +void makeGraph(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){ + if(i!=j && getDist(wlist[i], wlist[j])==1){ map[i][j] = 1; map[j][i] = 1; } } -int get_dist(string a, string b){ +int getDist(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++; + string longer, shorter; + + if(a.length() > b.length()){ + longer = a; + shorter = b; + } + else{ /* Also accounts for equal length */ + longer = b; + shorter = a; + } + dist += longer.length() - shorter.length(); + + for(int i=0; i<shorter.length(); i++) + if(shorter[i]!=longer[i]) + dist+=1; + return dist; } diff --git a/429/word.in b/429/word.in deleted file mode 100644 index b79b8e8..0000000 --- a/429/word.in +++ /dev/null @@ -1,67 +0,0 @@ -4 - -dip -lip -mad -map -maple -may -pad -pip -pod -pop -sap -sip -slice -slick -spice -stick -stock -* -spice stock -may pod - -dip -lip -mad -map -mapl -maple -may -pad -pip -pod -pop -sap -sip -slice -slick -spice -stick -stock -* -spice slick -may mad -map maple -maple map -map map - -mapl -maple -mba -mbal -mbale -mbple -* -mba mapl - -map -mapl -maple -mba -mbal -mbale -mbp -mbple -* -mba mapl @@ -3,9 +3,12 @@ * DONE 146 - Supposed to be solved with cpp stl, perhaps a c implementation of next_permutation will be more exciting? -* UNFINISHED 429 +* WORKING 429 - Word transformation: looks like a graph problem + - Appears under 'easy BFS' - Needs to be revisited -* WORKING 12532 -- On uhunt this problem is put under a 'tree-related structures', but not sure how a tree might be useful in this case - - Attempting a (naive) linear array first to see if it works (half expecting it to fail on time limit) +* UNFINISHED 12532 +- On uhunt this problem is put under 'tree-related structures', but not sure how a tree might be useful in this case + - A segment tree perhaps? +- Attempting a (naive) linear array first to see if it works (half expecting it to fail on time limit) + - Failed on TLE |