429 - Word Transformation

karakuritempya · Post by **karakuritempya** » Sat Dec 15, 2012 6:20 am

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

Mukit Chowdhury · Post by **Mukit Chowdhury** » Fri Feb 08, 2013 8:45 am

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 · Post by **Labib** » Thu Mar 14, 2013 12:25 pm

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 · Post by **brianfry713** » Thu Mar 14, 2013 9:24 pm

Compare each pair of words once before you start the BFS.

@ce · Post by **@ce** » Wed May 22, 2013 6:50 am

@deadangelx....your test cases are incorrect.

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.

udoy · Post by **udoy** » Thu Oct 03, 2013 10:28 pm

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 · Post by **brianfry713** » Tue Oct 08, 2013 1:37 am

Your code is throwing a seg fault on the sample input.

LazyTym · Post by **LazyTym** » Tue Aug 26, 2014 3:31 pm

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;
}

LazyTym · Post by **LazyTym** » Tue Aug 26, 2014 3:57 pm

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];
           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;
}

LazyTym · Post by **LazyTym** » Tue Aug 26, 2014 4:08 pm

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;
}

lighted · Post by **lighted** » Tue Aug 26, 2014 5:00 pm

Don't double post

brianfry713 · Post by **brianfry713** » Wed Aug 27, 2014 7:23 pm

You're not popping the front of the queue.

LazyTym · Post by **LazyTym** » Wed Aug 27, 2014 10:59 pm

thanks brianfry713

LazyTym · Post by **LazyTym** » Wed Aug 27, 2014 11:38 pm

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;
}

lighted · Post by **lighted** » Thu Aug 28, 2014 12:57 am

Input

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

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.

OJ Board

429 - Word Transformation

Re: 429 - Word Transformation

Re: 429 Word Transformation

Re: 429 Word Transformation

Re: 429 Word Transformation

Re: 429 - Word Transformation

wa in 429 – Word Transformation

Re: wa in 429 – Word Transformation

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

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

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

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

Re: 429 - Word Transformation

Re: 429 - Word Transformation

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

Re: 429 - Word Transformation