10102 - The path in the colored field

[helloneo]

cut

[Antonio Ocampo]

Hi Sedefcho

I modified a little bit my old code, now I pass your test but........ I still get WA.

This is my new code

Code: Select all

#include <iostream> 
#include <cstdio> 

using namespace std; 

int ab(int n) 
{ 
  if(n>0) 
   return n; 

  return -n; 
} 


int main() 
{ 
      char a[1000][1000]; 
      int t,max,min,i,j,lim,k,l,n; 

      while( scanf("%i",&n)==1 ) 
      { 
         for(i=0;i<n;++i) 
           scanf("\n%[^\n]\n",a[i]); 

         max=-1; 

         for(i=0;i<n;++i) 
         { 
           lim=strlen(a[i]);
           
           for(j=0;j<lim;++j) 
           { 
              if( a[i][j]=='1' ) 
              { 
                min=10000; 

                for(k=0;k<n;++k) 
                { 
                  for(l=0;l<lim;++l) 
                  { 
                     if( a[k][l]=='3') 
                     { 
                        t=ab(i-k)+ab(j-l); 

                        if(t<min) 
                        { 
                          min=t; 
                        } 
                     } 
                  } 
                } 
              } 
           } 

           if( min>max ) 
           { 
             max=min; 
           } 
         } 

         cout<<max<<"\n"; 
      } 

      return 0; 
} 

[scidong]

Code: Select all

#include<iostream.h>
#include<vector>
#include<math.h>
using namespace std;

void main(){
	int **a,i,j,c,min,max;
	vector<int> f1,f2,e1,e2;
	while(cin >> c){
		a = new int*[c];
		char d;
		for(i = 0; i<c; i++){
			a[i] = new int[c];
			for(j = 0; j<c; j++){
				cin >> d;
				if(d<'0'||d>'9'){
					j--;
				}else a[i][j] = d-'0';
			}
		}
		for(i = 0; i<c; i++){
			for(j = 0; j<c; j++){
				if(a[i][j] == 1){
					f1.push_back(i);
					f2.push_back(j);
				}if(a[i][j] == 3){
					e1.push_back(i);
					e2.push_back(j);
				}
			}
		}
		max=0;
		for(i = 0; i<f1.size(); i++){
			min=2147483647;
			for(j = 0; j<e1.size(); j++){
				if(abs(f1[i]-e1[i])+abs(f2[i]-e2[i])<min){
					min=abs(f1[i]-e1[i])+abs(f2[i]-e2[i]);
				}
			}
			if(max<min) max=min;
		}
		cout << max << endl;
		f1.resize(0);
		f2.resize(0);
		e1.resize(0);
		e2.resize(0);
		for(i = 0; i<c; i++) delete[] a[i];
		delete[] a;
	}
}

What`s wrong with this code?
Plz help me...
'Thx on your advice...'[/code]

[neno_uci]

Try the following test case:

Code: Select all

3
111
111
333

My AC program output:

Code: Select all

2

Your output:

Code: Select all

63

Hope this helps

[alamgir kabir]

Thank U very much Sapnil.

[sapnil]

What is the size of M ?????????

Thanks
Keep posting
Sapnil

[sapnil]

Ok get Acc now
>> 1009 sufficient

Thanks
Keep posting
Sapnil

[sapnil]

To alamgir

->you get RE because you take 2-d matrix of size 10000.
-> Why you take such a large value
-> 1009 is sufficient.


Thanks
Keep posting
Sapnil

[jahin]

why im getting TLE
can any one help me?

Code: Select all

#include <iostream>
#include <queue>

#define PR pair<int,int>
#define SS 1009
using namespace std;

int dist[SS][SS];
char in[SS][SS];
bool visited[SS][SS];

int main(){
	queue<PR> q,source;
	
	int dirx[]={1,0,-1,0};
	int diry[]={0,-1,0,1};
	
	int i,j,k,m,sz,final=1<<30,stx,sty;
	bool flag=0;
	vector<int> v;
	while(scanf("%d",&m)==1){
		v.clear();
		sz=m;
		for(i=0;i<m;i++){
			for(j=0;j<m;j++){
				cin>>in[i][j];
				if(in[i][j]=='1')source.push(make_pair(i,j));
			}
        }
		
		while(!source.empty()){
			
			PR pp=source.front();
			source.pop();
			stx=pp.first,sty=pp.second;
			memset(visited,false,sizeof(visited));
			memset(dist,0,sizeof(dist));
			q.push(make_pair(stx,sty));
			dist[stx][sty]=0;
			visited[stx][sty]=true;
			while(!q.empty()){
				PR p=q.front();
				q.pop();
				int px=p.first,py=p.second;
				for(i=0;i<4;i++){
					if(px+dirx[i]>=0 && px+dirx[i]<sz 
						&& py+diry[i]>=0 && py+diry[i]<sz && !visited[px+dirx[i]][py+diry[i]]){

						
						dist[px+dirx[i]][py+diry[i]]=dist[px][py]+1;
						visited[px+dirx[i]][py+diry[i]]=true;
						if(in[px+dirx[i]][py+diry[i]]=='3' && dist[px+dirx[i]][py+diry[i]]<final){
							final=dist[px+dirx[i]][py+diry[i]];
						}
                                                q.push(make_pair((px+dirx[i]),(py+diry[i])));
						
					}
				}
			}
			v.push_back(final);
		}
		sort(v.begin(),v.end());

		cout<<v[v.size()-1]<<endl;
	}
	return 0;
}

[Igor9669]

It is very strange!!!!
At first I have got WA, and I don't know why it was....
But when I added a condition :
if(max==0)while(1); I got accepted!
Who could tell me why this was happen?

[abid_iut]

I am getting CE
it is giving

code.cpp: In function 'int cal()':
code.cpp:19: error: 'abs' was not declared in this scope
code.cpp: At global scope:
code.cpp:29: error: '::main' must return 'int'

here is the code:

Code: Select all

#include<stdio.h>
#include<math.h>

#define MAXN 10000
char field[1000];
int o,t;

struct One{
	int x;
	int y;
}one[MAXN],three[MAXN];

int cal(){
	int i,j,d;
	int MAX=0,MIN;
	for(i=0;i<o;i++){
		MIN=32767;
		for(j=0;j<t;j++){
			d=abs(one[i].x - three[j].x) + abs(one[i].y - three[j].y);
			if(MIN>d)MIN=d;
		}
		if(MIN>MAX)MAX=MIN;
	}
	printf("%d\n",MAX);
	return 0;
}


void main(){
	int n,i,j;
	while(scanf("%d",&n)==1){
	i=o=t=0;
	while(n--){
		scanf("%s",field);
		for(j=0;field[j];j++){
			if(field[j]=='1'){
				one[o].x=i;
				one[o].y=j;
				o++;
			}
			else if(field[j]=='3'){
				three[t].x=i;
				three[t].y=j;
				t++;
			}
		}
		i++;
	}
	cal();
	}
}
		

pls help

[Articuno]

You used abs() but did not include the required header file <stdlib.h>. And try using this format for main()

Code: Select all

int main()
{
//code
return 0;
}

Good luck

[vahid sanei]

I got Acc in 0.030 when i use cin ,but i can`t use scanf for reading input ( i got wrong with scanf )
like this :

Code: Select all

	for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				scanf("%c",s[i][j]);
			}
			getchar();//For enter in end of each line
		}

how can i reduce time of mycode ?
thanks in advance

[Tausiq]

i don't know, what should i say !
this is my first post ..
verdict shows wrong ans.
i did check various input as far i can .. but couldn't find any bug
i've used bfs here
here is my code :

Code: Select all

#include <iostream.h>
#include <queue>
using namespace std;

struct node {
	int row;
	int column;
	int color;
	int value;
	char input;
} a [1010] [1010];

queue <node> q;

int m;

void reset ()
{
	for ( int i = 0; i < m; i++ ) {
		for ( int j = 0; j < m; j++ ) {
			a [i] [j].row = i;
			a [i] [j].column = j;
			a [i] [j].color = 0;
			a [i] [j].value = 9999;
		}
	}
}

int find () 
{
	int min = 9999;

	for ( int i = 0; i < m; i++ ) {
		for ( int j = 0; j < m; j++ ) {
			if ( a [i] [j].input == '3' ) {
				if ( a [i] [j].value < min )
					min = a [i] [j].value;
			}
		}
	}

	return min;
}

void set ( int x, int y )
{
	int r;
	int c;

	/* up */
	r = x - 1;
	c = y;

	if ( r >= 0 && a [r] [c].color == 0 ) { 
		a [r] [c].value = a [x] [y].value + 1;
		a [r] [c].color = 1;
		q.push (a [r] [c]);
	}

	/* right */
	r = x;
	c = y + 1;

	if ( c < m && a [r] [c].color == 0 ) {
		a [r] [c].value = a [x] [y].value + 1;
		a [r] [c].color = 1;
		q.push (a [r] [c]);
	}

	/* down */
	r = x + 1;
	c = y;

	if ( r < m && a [r] [c].color == 0 ) {
		a [r] [c].value = a [x] [y].value + 1;
		a [r] [c].color = 1;
		q.push (a [r] [c]);
	}

	/* left */
	r = x;
	c = y - 1;


	if ( c >= 0 && a [r] [c].color == 0 ) {
		a [r] [c].value = a [x] [y].value + 1;
		a [r] [c].color = 1;
		q.push (a [r] [c]);
	}
}

void bfs ()
{
	while ( !q.empty () ) {

		int r = q.front ().row;
		int c = q.front ().column;
		q.pop ();

		if ( a [r] [c].color != 2 ) {
			a [r] [c].color = 2;
			set ( r, c );
		}
	}
}

int main ()
{
	int i;

	while ( cin >> m ) {

		reset ();

		for ( i = 0; i < m; i++ ) {
			for ( int j = 0; j < m; j++ )
				cin >> a [i] [j].input;
		}

		int max = 0; 

		for ( i = 0; i < m; i++ ) {
			for ( int j = 0; j < m; j++ ) {
				if ( a [i] [j].input == '1' ) {
					reset ();
					a [i] [j].value = 0;
					q.push (a [i] [j]);
					bfs ();
				}

				int temp = find ();
				if ( temp > max )
					max = temp;
			}
		}

		cout << max << endl;
	}
	return 0;
}

plz help me .. thnx.

[Ratul Ahmed]

i cant understand why im getting TLE? pls help me.

Code: Select all

#include<stdio.h>


#define MAX 10000
#define INF 32767


int main()
{
    char ch;
    int M,I,J,K,L,D,R,C,max,min,cord1[MAX][2],cord3[MAX][2];
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
  */
    while( scanf("%d",&M)==1 )
    {
        while(getchar()!='\n');

        I=0;
        K=0;
        L=0;
        while(I<M)
        {
            J=0;
            while( (ch=getchar())!='\n'  )
            {
                if( ch=='1' )
                {
                    cord1[K][0]=I;
                    cord1[K][1]=J;
                    K++;
                    J++;
                }
                else if( ch=='2' )
                {
                    J++;
                }
                else if( ch=='3' )
                {
                    cord3[L][0]=I;
                    cord3[L][1]=J;
                    L++;
                    J++;
                }
            }
            I++;
        }

        max=0;
        for(I=0;I<K;I++)
        {
            min=INF;
            for(J=0;J<L;J++)
            {
            /*calculating distance*/
                R=cord1[I][0]-cord3[J][0];
                C=cord1[I][1]-cord3[J][1];
                if(R<0)
                    R=-R;
                if(C<0)
                    C=-C;

                D=R+C;
                if( min>D )
                {
                    min=D;
                }
            }

            if( max<min )
            {
                max=min;
            }
        }

        printf("%d\n",max);
    }


    return 0;
}