hmm Depth First search Actually I asked ths question there on lightoj forum... Admin replied "ur prog is not keeping track of visited states, to avoid exploring the same paths again and again.". I didn't understand how to keep track of visited states here bcz a character can be visited more than once..
On Thu, Mar 14, 2013 at 9:15 AM, ayman bs <[email protected]> wrote: > Could you elaborate on "The visited status of a node?" > > When you said DFS, did you mean Depth first search? I don't see why > you would need a DFS since at each letter you would need to check it's > neighbors and the letter itself. 9 if statements at most so make sure > you check your boundaries. > > Let me know where you still have difficulties. > > On Wed, Mar 13, 2013 at 2:14 PM, anup1pma <[email protected]> wrote: > > rather than posting source code.., I want to know that how to maintain > the > > visited status.. bcz I m not maintaining the visited status of a node > that's > > y my prog is giving TLE.. > > http://www.lightoj.com/volume_showproblem.php?problem=1434 > > > > > > > > > > On Wednesday, 13 March 2013 22:06:56 UTC+5:30, anup1pma wrote: > >> > >> hey m newbie in coding.. I think ur advise is very precious for me and > >> will be helpful in future.. > >> I gonna post comment version of this code... > >> thanking You :) > >> > >> On Wed, Mar 13, 2013 at 9:41 PM, ayman bs <[email protected]> wrote: > >>> > >>> Just an advice, especially when you want someone else to read your > >>> code, try to make your variable names meaningful and put comments that > >>> explain what every part is supposed to do, I guarantee you will get > >>> faster response and will even encourage you to debug your code > >>> yourself :) > >>> > >>> On Wed, Mar 13, 2013 at 11:10 AM, anup1pma <[email protected]> > >>> wrote: > >>> > hi > >>> > http://www.lightoj.com/volume_showproblem.php?problem=1434 > >>> > m solved this problem using DFS but getting TLE > >>> > here is my source code > >>> > > >>> > #include<iostream> > >>> > #include<vector> > >>> > #include<string> > >>> > #include<cstring> > >>> > #include<cstdio> > >>> > using namespace std; > >>> > > >>> > int indexx[26][1802]; > >>> > int arr[20];//0-DL:1-D:2-DR:3-L:4-R:5-UL:6-U:7-UR > >>> > int i,r,c; > >>> > char b[40][40]; > >>> > int vt[40][40]; > >>> > char ss[40]; > >>> > > >>> > int dfs(int rr,int cc,int idx) > >>> > { > >>> > int n=strlen(ss); > >>> > if(rr>0&&cc>0&&ss[idx+1]==b[rr-1][cc-1]) > >>> > { > >>> > > >>> > > >>> > if((idx+1==n-1)||dfs(rr-1,cc-1,idx+1)>=0) > >>> > {arr[idx]=0;return 50;} > >>> > > >>> > > >>> > } > >>> > if(rr>0&&ss[idx+1]==b[rr-1][cc]) > >>> > { > >>> > if((idx+1==n-1)||dfs(rr-1,cc,idx+1)>=0) > >>> > {arr[idx]=1;return 50;} > >>> > > >>> > } > >>> > if(rr>0&&cc<c-1&&ss[idx+1]==b[rr-1][cc+1]) > >>> > { > >>> > if((idx+1==n-1)||dfs(rr-1,cc+1,idx+1)>=0) > >>> > {arr[idx]=2;return 50;} > >>> > > >>> > } > >>> > if(cc>0&&ss[idx+1]==b[rr][cc-1]) > >>> > { > >>> > if((idx+1==n-1)||dfs(rr,cc-1,idx+1)>=0) > >>> > {arr[idx]=3;return 50;} > >>> > > >>> > } > >>> > if(cc<c-1&&ss[idx+1]==b[rr][cc+1]) > >>> > { > >>> > if((idx+1==n-1)||dfs(rr,cc+1,idx+1)>=0) > >>> > {arr[idx]=4;return 50;} > >>> > > >>> > } > >>> > if(rr<r-1&&cc>0&&ss[idx+1]==b[rr+1][cc-1]) > >>> > { > >>> > if((idx+1==n-1)||dfs(rr+1,cc-1,idx+1)>=0) > >>> > {arr[idx]=5;return 50;} > >>> > > >>> > } > >>> > if(rr<r-1&&ss[idx+1]==b[rr+1][cc]) > >>> > { > >>> > if((idx+1==n-1)||dfs(rr+1,cc,idx+1)>=0) > >>> > {arr[idx]=6;return 50;} > >>> > > >>> > } > >>> > if(rr<r-1&&cc<c-1&&ss[idx+1]==b[rr+1][cc+1]) > >>> > { > >>> > if((idx+1==n-1)||dfs(rr+1,cc+1,idx+1)>=0) > >>> > {arr[idx]=7;return 50;} > >>> > > >>> > } > >>> > if(ss[idx+1]==b[rr][cc]) > >>> > { > >>> > if((idx+1==n-1)||dfs(rr,cc,idx+1)>=0) > >>> > {arr[idx]=8;return 50;} > >>> > > >>> > } > >>> > return -6; > >>> > > >>> > } > >>> > > >>> > > >>> > int main() > >>> > { > >>> > int cases,cs,N,i,j,pp; > >>> > int ft,ac,ar,fff,k; > >>> > char ch; > >>> > //string name; > >>> > scanf("%d",&cases); > >>> > for(int I=0;I<cases;I++) > >>> > { > >>> > scanf("%d %d",&r,&c); > >>> > getchar(); > >>> > for(i=0;i<r;i++) > >>> > { > >>> > scanf("%s",b[i]); > >>> > } > >>> > memset(indexx,-1,sizeof(indexx)); > >>> > for(i=0;i<r;i++){ > >>> > for(j=0;j<c;j++) > >>> > { > >>> > k=0; > >>> > while(indexx[(int)(b[i][j]-'A')][k]>=0) > >>> > k+=2; > >>> > indexx[(int)(b[i][j]-'A')][k]=i; > >>> > indexx[(int)(b[i][j]-'A')][k+1]=j; > >>> > > >>> > //cout<<indexx[b[i][j]-'A'][k]<<" "; > >>> > } > >>> > // cout<<endl; > >>> > } > >>> > > >>> > > >>> > > >>> > scanf("%d",&N); > >>> > getchar(); > >>> > printf("Case %d:\n",I+1); > >>> > > >>> > > >>> > //cin.get(); > >>> > while(N--) > >>> > { > >>> > > >>> > pp=0; > >>> > scanf("%s",ss); > >>> > ch=ss[0]; > >>> > ar=-1; > >>> > ac=-1; > >>> > fff=1; > >>> > k=0; > >>> > while(indexx[(int)(ch-'A')][k]>=0) > >>> > { > >>> > i=indexx[(int)(ch-'A')][k]; > >>> > j=indexx[(int)(ch-'A')][k+1]; > >>> > //cout<<i<<" "<<j<<endl; > >>> > pp=dfs(i,j,0); > >>> > if(pp==50) > >>> > { > >>> > ar=i; > >>> > ac=j; > >>> > > >>> > break; > >>> > } > >>> > k+=2; > >>> > } > >>> > > >>> > > >>> > if(ar>=0&&ac>=0) > >>> > { > >>> > printf("%s found: (%d,%d)",ss,ar+1,ac+1); > >>> > for(i=0;i<strlen(ss)-1;i++) > >>> > { > >>> > switch(arr[i]) > >>> > { > >>> > case 0: > >>> > printf(", UL"); > >>> > break; > >>> > case 1: > >>> > printf(", U"); > >>> > break; > >>> > case 2: > >>> > printf(", UR"); > >>> > break; > >>> > case 3: > >>> > printf(", L"); > >>> > break; > >>> > case 4: > >>> > printf(", R"); > >>> > break; > >>> > case 5: > >>> > printf(", DL"); > >>> > break; > >>> > case 6: > >>> > printf(", D"); > >>> > break; > >>> > case 7: > >>> > printf(", DR"); > >>> > break; > >>> > case 8: > >>> > printf(", *"); > >>> > break; > >>> > > >>> > > >>> > } > >>> > } > >>> > printf("\n"); > >>> > } > >>> > else > >>> > printf("%s not found\n",ss); > >>> > } > >>> > } > >>> > > >>> > return 0; > >>> > } > >>> > > >>> > > >>> > waiting for ur reply.. > >>> > thanks :) > >>> > > >>> > regards > >>> > Anup Singh > >>> > > >>> > -- > >>> > You received this message because you are subscribed to the Google > >>> > Groups > >>> > "Google Code Jam" group. > >>> > To unsubscribe from this group and stop receiving emails from it, > send > >>> > an > >>> > email to [email protected]. > >>> > To post to this group, send email to [email protected]. > >>> > To view this discussion on the web visit > >>> > https://groups.google.com/d/msg/google-code/-/8YbMY3tD5-gJ. > >>> > For more options, visit https://groups.google.com/groups/opt_out. > >>> > > >>> > > >>> > >>> -- > >>> You received this message because you are subscribed to the Google > Groups > >>> "Google Code Jam" group. > >>> To unsubscribe from this group and stop receiving emails from it, send > an > >>> email to [email protected]. > >>> To post to this group, send email to [email protected]. > >>> For more options, visit https://groups.google.com/groups/opt_out. > >>> > >>> > >> > > -- > > You received this message because you are subscribed to the Google Groups > > "Google Code Jam" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to [email protected]. > > To post to this group, send email to [email protected]. > > To view this discussion on the web visit > > https://groups.google.com/d/msg/google-code/-/Fk6G_oU9WU4J. > > > > For more options, visit https://groups.google.com/groups/opt_out. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
