Page 3 of 6

Re: 429

Posted: Sat Dec 11, 2010 5:15 pm
by 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;
}

Re: 429 (Why RE??)

Posted: Thu Oct 13, 2011 11:32 am
by 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??

Re: 429 Word Transformation

Posted: Tue Oct 18, 2011 4:42 pm
by zyz913614263
is 'ba' and 'cb' right?

Re: 429 Word Transformation

Posted: Tue Oct 18, 2011 6:44 pm
by zyz913614263
zyz913614263 wrote: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
:D

429 - Word Transformation

Posted: Mon Nov 28, 2011 4:27 pm
by 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.

Re: 429 Word Transformation

Posted: Sun May 27, 2012 12:08 pm
by 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;
}

Re: 429 Word Transformation

Posted: Fri Jun 01, 2012 12:37 am
by 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

Re: 429 Word Transformation

Posted: Fri Jun 01, 2012 6:34 am
by mathgirl
Thanks ! The problem was in reading the newlines after each test case. Got AC now.

Re: 429 Word Transformation

Posted: Mon Jul 23, 2012 5:02 pm
by 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.

Re: 429 Word Transformation

Posted: Mon Jul 23, 2012 11:38 pm
by brianfry713
Clear your queue between test cases.

Re: 429 Word Transformation

Posted: Mon Nov 26, 2012 6:45 pm
by 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;
}

Re: 429 Word Transformation

Posted: Tue Nov 27, 2012 6:37 pm
by ?????? ????

Code: Select all

Remove After Accepted

Re: 429 Word Transformation

Posted: Fri Nov 30, 2012 9:07 pm
by brianfry713
naved92, did you mean to have a call to init()?

Re: 429 - Word Transformation

Posted: Fri Dec 14, 2012 3:51 pm
by karakuritempya
I am getting TLE for this problem :( . Does it matter to use getline(cin) ?

Re: 429 - Word Transformation

Posted: Fri Dec 14, 2012 7:51 pm
by 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.