429 - Word Transformation
Moderator: Board moderators
-
- 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
-
- 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 ...![:x](./images/smilies/icon_mad.gif)
![:x](./images/smilies/icon_mad.gif)
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 ...
![:x](./images/smilies/icon_mad.gif)
Re: 429 Word Transformation
I'm getting TLE on this problem...
Any suggestion on what to do to avoid it???
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;
}
-
- 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!
Re: 429 - Word Transformation
@deadangelx....your test cases are incorrect.
You are changing the word length.Each successive word differs from the previous word in only a single character position while the word length remains the same.
-@ce
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
![:cry:](./images/smilies/icon_cry.gif)
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;
}
-
- 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!
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];
if(addEdge(s1,s2)){
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;
}
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...............?
![:(](./images/smilies/icon_frown.gif)
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];
if(addEdge(s1,s2)){
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;
}
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];
if(addEdge(s1,s2)){
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;
}
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
-
- 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!
Re: 429 - Word Transformation
thanks brianfry713
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];
if(addEdge(s1,s2)){
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;
}
Re: 429 - Word Transformation
Input
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.
Code: Select all
2
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
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice stock
may pod
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