429 - Word Transformation

[Obaida]

Why i am getting TLE? Any one please help me

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<cmath>
#include<sstream>
#include<fstream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<list>
#include<bitset>
#include<algorithm>
#include<functional>
using namespace std;

int main(){
    int t,cost;
    scanf("%d",&t);
    while(t--){
        string s;
        char line[25];
        vector<string>D;
        while(scanf("%s",line)){
            if(line[0]=='*')break;
            D.push_back(line);
        }
        gets(line);
        while(gets(line)){
            if(!line[0])break;
            stringstream is(line);
            string a,b;
            is>>a>>b;
            vector<string>d;
            for(int i = 0;i<D.size();++i)if(D[i].size()==a.size())d.push_back(D[i]);
            queue< pair<string,int> >Q;
            set< string >S;
            Q.push( make_pair(a,0) );
            S.insert(a);
            while(Q.size()){
                s = Q.front().first;
                cost = Q.front().second;
                Q.pop();
                if(s==b){
                    printf("%s %s %d\n",a.c_str(),b.c_str(),cost);
                    break;
                }
                for(int i = 0;i<d.size();++i){
                    int c = 0;
                    for(int j = 0;j<d[i].size();++j)if(d[i][j]!=s[j])++c;
                    if(S.find(d[i])!=S.end() || c!=1)continue;
                    S.insert(d[i]);
                    Q.push( make_pair(d[i],cost+1) );
                }
            }
        }if(t)puts("");
    }
    return 0;
}

[MAMU]

My code:

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>

char s[220][15];bool sd[220][220];int dis[220];

inline void init_d(int n){for(int i=0;i<n;i++)dis[i]=24748364;}

void bfs(int i,int j,int n)
{
	for(;j<n;j++)
	{
		if(sd[i][j]==1&&dis[j]>dis[i]+1)
		{
			dis[j]=dis[i]+1;
			bfs(i,j+1,n);
			bfs(j,0,n);
			break;
		}
	}
}

int main()
{
	int f=0;
	char s1[15],s2[15];
	int t,z=1,i,j,k,a,n,e,g;
	gets(s1);
	t=atoi(s1);
	while(z++<=t)
	{
		if(z>2)putchar(10);
		i=0;
		while(gets(s[i])!=NULL&&strcmp(s[i],"*")!=0)
		{
			for(j=0;j<i&&s[i][0]!=0;j++)
			{
				if(strlen(s[i])==strlen(s[j]))
				{
					for(k=0,a=0;s[i][k]!=0;k++)
					{
						if(s[i][k]!=s[j][k])a++;
						if(a>=2)break;
					}
					if(a==1){sd[i][j]=1;sd[j][i]=1;}
				}
			}
			if(s[i][0]!=0)
				i++;
		}
		n=i;
		while(gets(s1)!=NULL&&s1[0]!=0)
		{
			i=strlen(s1)/2;s1[i]=0;
			for(i++,j=0;s1[i]!=0;i++,j++)
				s2[j]=s1[i];
			s2[j]=0;

			for(i=0,f=0;i<n;i++)
			{
				if(strcmp(s[i],s1)==0){e=i;if(f==2)break;f=1;}
				if(strcmp(s[i],s2)==0){g=i;if(f==1)break;f=2;}
			}
			init_d(n);
			dis[e]=0;
			bfs(e,0,n);
			printf("%s %s %d\n",s1,s2,dis[g]);
		}
	}
	return 0;
}

I just solve about 20 graph(dfs,bfs) problem... but this type of problem give me about 50 RTE... most of the case... not for stack over flow... I think in this problem, I cant read the input file properly...
Can anybody help??

[zyz913614263]

is 'ba' and 'cb' right?

[zyz913614263]

is 'ba' and 'cb' right?

I got the AC
the transfer is
abc to abd right
but
abc to bad wrong
abc to abcd wrong

[outsbook]

BFS problem

1. Input all dictionary words to string array word[]
2. Find adjacency list for all word.
ab adjacency can be ac, ad,....,cb,db, and so on. i.e. only one character is different and two word length are same.
but ab adjacency can not be ab,abc,dab,cd and so on.
3. Now run BFS from start word to end word and find the move from start to end. i.e. shortest path.

[mathgirl]

I m getting RTE for this one. I tried with sample I/O and my code works.

Code: Select all

#include<stdio.h>
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

struct word
{
	char w[20];
};

vector<word> dict;
vector<vector<int> > conn;
vector<bool> chosen;
vector<int> dist;

bool same(char *a,char *b)
{
	if(strlen(a) != strlen(b))
		return false;

	for(int i = 0;i<strlen(a);i++)
	{
		if(a[i] != b[i])
			return false;
	}
	return true;
}

bool compare(char *a,char *b)
{
	if(strlen(a) != strlen(b))
		return false;

	int diff = 0;
	for(int i = 0;i<strlen(a);i++)
	{
		if(a[i] != b[i])
			diff++;

		if(diff > 1)
			return false;
	}
	return true;
}

void mindist(int dest,int d)
{
	vector<int> next;
	next.push_back(dest);
	int n = next.front();
	dist[n] = min(dist[n],d + 1);
	while(!next.empty())
	{
		n = next.front();
		if(!chosen[n])
		{
			chosen[n] = true;
			for(int i = 0;i < conn[n].size();i++)
			{
				dist[conn[n][i]] = min(dist[conn[n][i]],dist[n] + 1);
				next.push_back(conn[n][i]);
			}
		}

		next.erase(next.begin());
	}
}

int main()
{
	int t,re;
	re = scanf("%d",&t);
	bool first = true;

	while(t--)
	{
		while(getchar() != '\n');
		while(getchar() != '\n');

		char temp[100];
		
		while(scanf("%s",temp) && !same(temp,"*"))
		{
			word obj;
			strcpy(obj.w,temp);
			dict.push_back(obj);
			conn.push_back(vector<int>());
			int cur = dict.size() - 1;

			for(int i = 0;i < dict.size() - 1;i++)
			{
				if(compare(obj.w,dict[i].w) == 1)
				{
					conn[i].push_back(cur);
					conn[cur].push_back(i);
				}
			}
		}

		while(getchar() != '\n');

		if(!first)
			printf("\n");
		first = false;

		char start[20],dest[20];
		while(gets(temp) && strlen(temp))
		{
			char *pch;
	        pch = strtok(temp, " ");
	        strcpy(start,pch);
	        pch = strtok (NULL, " ");
	        strcpy(dest,pch);
			
			chosen.assign(dict.size(),false);
			dist.assign(dict.size(),1000);
			
			int s = -1,d = -1,i = 0;
			
			for(int i = 0;i < dict.size();i++)
			{
				if(same(start,dict[i].w))
				{	
					s = i;
					break;
				}
			}
			
			for(int i = 0;i < dict.size();i++)
			{
				if(same(dest,dict[i].w))
				{	
					d = i;
					break;
				}
			}

			int len = 0;

			mindist(d,-1);
			len = dist[s];
			printf("%s %s %d\n",start,dest,len);
		}

		dict.clear();
		conn.clear();
	}
	return 0;
}

[brianfry713]

Try this 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
*
dip lip

[mathgirl]

Thanks ! The problem was in reading the newlines after each test case. Got AC now.

[pranon]

``WA" on this problem as well, with no apparent bugs apparent to me. Will be greatful for any help.

Code: Select all

Code removed. Should always remember to makenull() my queue. :D

Thanks in advance.

[brianfry713]

Clear your queue between test cases.

[naved92]

WA...cant fix the bug

Code: Select all

#include<cstdio>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
using namespace std;


char L[1024];
vector<string>graph;

int adjmatrix[256][256],n;
 bool visited[256];
 int dist[256];


void init()
{ n=0;
    graph.clear();
for(int i=0;i<256;i++)
  for(int j=0;j<256;j++)
    adjmatrix[i][j]=0;

}

bool is_dif_one(string a,string b)
{
    if(a.size() !=b.size())return false;
    int total=0;

    for(int i=0;i<a.size();i++)
     if(a[i]!=b[i])total++;
     if(total==1)return true;
     return false;
}
void make_a_graph()
{
  int i,j;

  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    {
        if(  is_dif_one(graph[i],graph[j])==1)adjmatrix[i][j]=1;

    }
}

int MAP(string &a)
{
    for(int i=0;i<n;i++)
    if(graph[i]==a)return i;

    return -1;
}
int main()
{

    int tc;
    gets(L);
    tc=atoi(L);

    while(tc--)
     {

         gets(L);

         istringstream IS;

         string word,source,end;

       //  map<string,int>MAP;

         int tot=0;
         while(gets(L))
         {
             IS.clear();
             IS.str(L);
             IS>>word;
             if(word=="*")break;
             graph.push_back(word);



         }

         n=graph.size();
         make_a_graph();



        while(gets(L))
        {
            IS.clear();
            IS.str(L);
            if(IS>>source>>end){

                /*BFS*/

                int S=MAP(source),D=MAP(end);

                queue<int>BFS;

               // memset(distance,-1,sizeof(distance));
              //  memset(visited,false,sizeof(visited));

for(int i=0;i<n;i++)
   {dist[i]=23456;visited[i]=false;}
                BFS.push(S);
                visited[S]=true;
                dist[S]=0;


                while(!BFS.empty())
                     {
                         int F=BFS.front();
                         BFS.pop();
                         if(F==D)break;
                         for(int i=0;i<n;i++)
                           {
                               int C=i;
                               if(visited[C]==false && adjmatrix[F][C]==1)
                                  { BFS.push(C);
                                      visited[C]=true;
                                      dist[C]=dist[F]+1;

                                  }
                           }
                     }
                  cout<<source<<" "<<end<<" "<<dist[D]<<endl;


                                                 }
        else break;
        }

        if(tc!=0)cout<<endl;
     }

return 0;
}

[?????? ????]

Code: Select all

Remove After Accepted

[brianfry713]

naved92, did you mean to have a call to init()?

[karakuritempya]

I am getting TLE for this problem . Does it matter to use getline(cin) ?

[brianfry713]

I don't think that's the cause of your TLE. My AC code uses getline(cin,str) to read the starting and ending words, and cin >> str to read the dictionary.