## 429 - Word Transformation

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

karakuritempya
New poster
Posts: 3
Joined: Sun Oct 21, 2012 10:34 am

### Re: 429 - Word Transformation

thanks, i've improved my algorithm and got ac now

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 429 Word Transformation

The pair of words of the second section of the given input will always be of same length...
It pains me a lot ... I thought it can be of different length after seeing a post ... Why this type of confusing post is allowed ...

Labib
New poster
Posts: 12
Joined: Tue Mar 05, 2013 4:49 pm

### Re: 429 Word Transformation

I'm getting TLE on this problem...
Any suggestion on what to do to avoid it???

Code: Select all

``````# include <cstdio>
# include <cstring>
# include <iostream>
# include <vector>
# include <string>
# include <map>
# include <sstream>
# include <queue>
# include <algorithm>

using namespace std;

struct two {
string s;
int c;
};

vector <string> s[15];
map <string, int> m;

int diff (string s1, string s2, int sz)
{
int i, j=0;
for (i = 0; i < sz; i++)
{
if (s1[i] != s2[i])
j++;
}
return j;
}

void bfs (string s1, string s2, int sz)
{
//cout << s1 << " " <<  s2 << endl;
int v[205], i, j, k;
queue <two> q;
two t1, t2;

t1.s = s1;
t1.c = 0;
q.push (t1);

memset (v, 0, sizeof (v));
while (!q.empty())
{
t1 = q.front();
q.pop();

if (v[m[t1.s]]) continue;
v[m[t1.s]] = 1;
if (t1.s == s2) break;

for (i=0; i<(int)s[sz].size(); i++)
{
if (v[m[s[sz][i]]]) continue;
if (diff (s[sz][i],t1.s, sz) == 1)
{
t2.s = s[sz][i];
t2.c = t1.c + 1;
q.push (t2);
}
}
}
//cout << s1 << " " << s2 << " " << t1.c << endl;
printf ("%s %s %d\n", s1.c_str(), s2.c_str(), t1.c);
return;
}

int main ()
{
int t, i, j, k, sz;
string s1, s2, s3, star ="*";
char str[100];

cin >> t;
while (t--)
{
while (1)
{
cin >> s1;
if (s1 == star) break;

sz = (int)s1.size();
s[sz].push_back (s1);
}

for (i = 1; i <= 10; i++){
sort (s[i].begin(), s[i].end());
for (j = 0; j < (int) s[i].size(); j++)
m[s[i][j]] = j;
}
gets (str); // dummy
while (gets (str) != NULL)
{
if ((int)strlen(str) == 0) break;
s3 = str;
stringstream ss;
ss << s3;
ss >> s1;
ss >> s2;
sz = (int) s1.size();

bfs (s1, s2, sz);
}

if (t) cout << endl;
for (i = 0; i < 15; i++) s[i].clear();
m.clear();
}
return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 429 Word Transformation

Compare each pair of words once before you start the BFS.
Check input and AC output for thousands of problems on uDebug!

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 429 - Word Transformation

Each successive word differs from the previous word in only a single character position while the word length remains the same.
You are changing the word length.
-@ce

udoy
New poster
Posts: 7
Joined: Sat Sep 28, 2013 11:27 am

### wa in 429 – Word Transformation

any one help me...........i am getting wa ...but cant get the reason........i am preety much confident about almost all the test cases......thanks in avdance for replying

Code: Select all

``````#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define max 30000
#define valid(i,j,x,y) (i>=0 && i<x &&j<y && j>=0 )

using namespace std;

char str[max][max],flag[max][max];

vector <string>graph[1000];
//vector<string>graph;
map<string,int>m2,distance1,taken;

int  diff(string x,string y);

int r,hell,count;
map<string,string>parent;

void bfs(string src,string dest)
{
int j,i;
int len=src.length();
// printf("%d\n",len);
string u,v;
queue <string>Q;
taken[src]=1;
distance1[src]=0;
if(src==dest)
{
distance1[dest]=0;
return ;
}
Q.push(src);
while(!Q.empty())
{
u=Q.front();
for (i=0; i<graph[len].size(); i++ )
{
v=graph[len][i];
if(diff(u,v)==1)

if(taken[v]==0)
{

distance1[v]=distance1[u]+1;
taken[v]=1;
Q.push(v);
if(v==dest)
{
//   cout<<"paisi"<<endl;
return;
}
}

}

Q.pop();      ;
}
return;

}

int main()
{
int a,b,i,c,d,e,l,flag=0;

string x,y;
scanf("%d",&a);
//  getchar();
for (; a-- ; )
{
i=10000;
for (; i--; )
graph[i].clear();
//  parent.clear();
taken.clear();
distance1.clear();
for (int i=0; cin>>x; i++ )
{

if(x=="*")
break;
l=x.length();

graph[l].push_back(x);

}
//    if(flag)
//    cout<<endl;
//  flag=1;
getchar();
string str;
istringstream iss;
//  char c=0;
for (; getline(cin,str) && str.length(); )
{
//  if(c)
//      cout<<endl;
//  c=0;
istringstream iss(str);
iss>>x>>y;

//  if(x!=y)
{
bfs(x,y);
cout<<x<<" "<<y<<" "<<distance1[y]<<endl;
}
// else cout<<x<<" "<<y<<" 0"<<endl<<endl;
}
// cout<<"ses"<<endl;
if(a)
cout<<endl;

}
return 0;    ;
}

int diff(string x,string y)
{
int count=0;
for (int i=0;i<x.length() ;i++ )

{
if(x[i] !=y[i])
count++;
}
;
return count;

}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: wa in 429 – Word Transformation

Your code is throwing a seg fault on the sample input.
Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### why bfs gets infinity loop.......?pls help........

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<queue>

using namespace std;
string L[250];
vector<vector<int> > graph(250);
map<string,int>m;
int *dis;

int addEdge(string x,string y)
{
int num=0,len1,len2;
len1=x.size();
len2=y.size();

if(len1!=len2) return 0;
else {
for(int i=0;i<len1;i++)
{
if(x[i]!=y[i]) num++;
if(num>1) return 0;
}
return 1;
}
}

void formGraph(int c)
{
string s1,s2,len1,len2;
for(int i=0;i<c;i++) cout<<m[L[i]]<<" ";
cout<<endl;
for(int i=0;i<c;i++)
{
s1=L[i];
for(int j=i+1;j<c;j++)
{
s2=L[j];
graph[m[s1]].push_back(m[s2]);
graph[m[s2]].push_back(m[s1]);
}
}
}
for(int i=0;i<c;i++)
{
cout<<i<<"->";
for(int j=0;j<graph[i].size();j++) cout<<graph[i][j]<<" ";
cout<<endl;
}
}
void bfs(int s,int d,int v)
{
cout<<s<<d<<endl;
queue<int>q;
int p;
int *visited=new int[v];
dis=new int[v];
for(int i=0;i<=v;i++)
{
visited[i]=0;
dis[i]=0;
}

q.push(s);
visited[s]=1;
//cout<<"fuck"<<endl;
dis[s]=1;
int flag=0;
while(!q.empty())
{
p=q.front();
cout<<p<<endl;
for(int i=0;i<graph[p].size();i++)
{
int x=graph[p][i];
//cout<<graph[p][i]<<endl;
if(visited[x]==0)
{
cout<<graph[p][i]<<endl;

q.push(x);
dis[x]=dis[p]+1;
visited[x]=1;

if(x==d)
{
flag=1;
break;
}
}
}
if(flag==1) break;

}

}

int main()
{
//freopen("fuck in.txt","r",stdin);
//freopen("fuck out.txt","w",stdout);

int test;
cin>>test;

for(int i=0;i<test;i++)
{
string x,source,destin;
int count_s=0;
while(1)
{
cin>>x;
if(x=="*") break;
m[x]=count_s;
L[count_s]=x;
count_s++;

}
formGraph(count_s);
cin>>source>>destin;

int s,d;
s=m[source];
d=m[destin];
bfs(s,d,count_s);
//cout<<dis[d]<<endl;
}
return 0;
}

``````

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### why bfs gets infinity loop.......?pls help........

this is not a final code for this problem but i want to know why bfs getting infinite...............?

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<queue>

using namespace std;
string L[250];
vector<vector<int> > graph(250);
map<string,int>m;
int *dis;

int addEdge(string x,string y)
{
int num=0,len1,len2;
len1=x.size();
len2=y.size();

if(len1!=len2) return 0;
else {
for(int i=0;i<len1;i++)
{
if(x[i]!=y[i]) num++;
if(num>1) return 0;
}
return 1;
}
}

void formGraph(int c)
{
string s1,s2,len1,len2;
for(int i=0;i<c;i++) cout<<m[L[i]]<<" ";
cout<<endl;
for(int i=0;i<c;i++)
{
s1=L[i];
for(int j=i+1;j<c;j++)
{
s2=L[j];
graph[m[s1]].push_back(m[s2]);
graph[m[s2]].push_back(m[s1]);
}
}
}
for(int i=0;i<c;i++)
{
cout<<i<<"->";
for(int j=0;j<graph[i].size();j++) cout<<graph[i][j]<<" ";
cout<<endl;
}
}
void bfs(int s,int d,int v)
{
cout<<s<<d<<endl;
queue<int>q;
int p;
int *visited=new int[v];
dis=new int[v];
for(int i=0;i<=v;i++)
{
visited[i]=0;
dis[i]=0;
}

q.push(s);
visited[s]=1;
//cout<<"fuck"<<endl;
dis[s]=1;
int flag=0;
while(!q.empty())
{
p=q.front();
cout<<p<<endl;
for(int i=0;i<graph[p].size();i++)
{
int x=graph[p][i];
//cout<<graph[p][i]<<endl;
if(visited[x]==0)
{
cout<<graph[p][i]<<endl;

q.push(x);
dis[x]=dis[p]+1;
visited[x]=1;

if(x==d)
{
flag=1;
break;
}
}
}
if(flag==1) break;

}

}

int main()
{
//freopen("fuck in.txt","r",stdin);
//freopen("fuck out.txt","w",stdout);

int test;
cin>>test;

for(int i=0;i<test;i++)
{
string x,source,destin;
int count_s=0;
while(1)
{
cin>>x;
if(x=="*") break;
m[x]=count_s;
L[count_s]=x;
count_s++;

}
formGraph(count_s);
cin>>source>>destin;

int s,d;
s=m[source];
d=m[destin];
bfs(s,d,count_s);
//cout<<dis[d]<<endl;
}
return 0;
}
``````

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### why bfs gets infinity loop.......?pls help........

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<queue>

using namespace std;
string L[250];
vector<vector<int> > graph(250);
map<string,int>m;
int *dis;

int addEdge(string x,string y)
{
int num=0,len1,len2;
len1=x.size();
len2=y.size();

if(len1!=len2) return 0;
else {
for(int i=0;i<len1;i++)
{
if(x[i]!=y[i]) num++;
if(num>1) return 0;
}
return 1;
}
}

void formGraph(int c)
{
string s1,s2,len1,len2;
for(int i=0;i<c;i++) cout<<m[L[i]]<<" ";
cout<<endl;
for(int i=0;i<c;i++)
{
s1=L[i];
for(int j=i+1;j<c;j++)
{
s2=L[j];
graph[m[s1]].push_back(m[s2]);
graph[m[s2]].push_back(m[s1]);
}
}
}
for(int i=0;i<c;i++)
{
cout<<i<<"->";
for(int j=0;j<graph[i].size();j++) cout<<graph[i][j]<<" ";
cout<<endl;
}
}
void bfs(int s,int d,int v)
{
cout<<s<<d<<endl;
queue<int>q;
int p;
int *visited=new int[v];
dis=new int[v];
for(int i=0;i<=v;i++)
{
visited[i]=0;
dis[i]=0;
}

q.push(s);
visited[s]=1;
//cout<<"fuck"<<endl;
dis[s]=1;
int flag=0;
while(!q.empty())
{
p=q.front();
cout<<p<<endl;
for(int i=0;i<graph[p].size();i++)
{
int x=graph[p][i];
//cout<<graph[p][i]<<endl;
if(visited[x]==0)
{
cout<<graph[p][i]<<endl;

q.push(x);
dis[x]=dis[p]+1;
visited[x]=1;

if(x==d)
{
flag=1;
break;
}
}
}
if(flag==1) break;

}

}

int main()
{
//freopen("fuck in.txt","r",stdin);
//freopen("fuck out.txt","w",stdout);

int test;
cin>>test;

for(int i=0;i<test;i++)
{
string x,source,destin;
int count_s=0;
while(1)
{
cin>>x;
if(x=="*") break;
m[x]=count_s;
L[count_s]=x;
count_s++;

}
formGraph(count_s);
cin>>source>>destin;

int s,d;
s=m[source];
d=m[destin];
bfs(s,d,count_s);
//cout<<dis[d]<<endl;
}
return 0;
}``````

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: why bfs gets infinity loop.......?pls help........

Don't double post
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 429 - Word Transformation

You're not popping the front of the queue.
Check input and AC output for thousands of problems on uDebug!

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### Re: 429 - Word Transformation

thanks brianfry713

LazyTym
New poster
Posts: 31
Joined: Tue Jun 24, 2014 9:10 pm

### Re: RTE ...........429 - Word Transformation!!!!!!!!!!!!

Code: Select all

``````]
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<queue>

using namespace std;
string L[250];
vector<vector<int> > graph(250);
map<string,int>m;
int *dis;

int addEdge(string x,string y)
{
int num=0,len1,len2;
len1=x.size();
len2=y.size();

if(len1!=len2) return 0;
else {
for(int i=0;i<len1;i++)
{
if(x[i]!=y[i]) num++;
if(num>1) return 0;
}
return 1;
}
}

void formGraph(int c)
{
string s1,s2,len1,len2;

for(int i=0;i<c;i++)
{
s1=L[i];
for(int j=i+1;j<c;j++)
{
s2=L[j];
graph[m[s1]].push_back(m[s2]);
graph[m[s2]].push_back(m[s1]);
}
}
}
}
int bfs(int s,int d,int v)
{
queue<int>q;
int p;
int visited[250];
dis=new int[v];
for(int i=0;i<=v;i++)
{
visited[i]=0;
dis[i]=0;
}

q.push(s);
visited[s]=1;

dis[s]=0;
int flag=0;
while(!q.empty())
{
p=q.front();
q.pop();

for(int i=0;i<graph[p].size();i++)
{
int x=graph[p][i];

if(visited[x]==0)
{
q.push(x);
dis[x]=dis[p]+1;
visited[x]=1;

if(x==d) return 1;
}
}

}

}

int main()
{

int test;
cin>>test;

for(int i=0;i<test;i++)
{
string x,source,destin;
int count_s=0;
while(1)
{
cin>>x;
if(x=="*") break;
m[x]=count_s;
L[count_s]=x;
count_s++;

}
formGraph(count_s);
while(cin>>source>>destin)
{

int s,d;
s=m[source];
d=m[destin];
bfs(s,d,count_s);
cout<<source<<" "<<destin<<" "<<dis[d]<<endl;
}

}
return 0;
}

``````

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 429 - Word Transformation

Input

Code: Select all

``````2

dip
lip
map
maple
may
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice stock
may pod

dip
lip
map
maple
may
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice stock
may pod``````
Each test case except last is followed by a blank line. Reading source and destination must stop when reaches blank line.
Your program doesn't stop and get RE. Also clear map after each case.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman