10102 - The path in the colored field

[wenzhi cai]

I can't understand the problem.Can anyone tell me?

[AlexandreN]

I was wrong.

[AlexandreN]

Finally I understand this problem.
You have to find de maximun of the minimun paths from one position with a '1' to one position with a '3'.

[henar2]

I have tried to solve this problem but I am getting Runtime Error (SIGSEGV). And I have been watching the statistics and there are a lot of Runtime Error.
Which is the biggest number of rows and columns?
Any hint about Runtime Error?
Could the numbers in the table be separated by spaces or blank lines?

thank you in advance.

[Yarin]

It can probably be quite high. Use dynamic allocation, I do something like this:

char *sq;

while (scanf("%d",&m)==1) {
sq=malloc(m*m+1);
for(i=0;i<m;i++)
scanf("%s",sq+i*m);
...
}

[Larry]

Can someone post some inputs? I use simple BFS and get WA...

[Larry]

Nevermind.. typo..

[Amir Aavani]

hi Larry

i wonder why you use BFS.
you could easily calculate the cost of reaching from any 1 to any 3,
by Abs(1.x- 3.x)+ Abs (1.y- 3.y) and then find the minimum for every 1 in the table.
and at last find the maximum of all this numbers.

[Larry]

Ya I know, after I submit it and see all these 0.00's... =) ah well

[Shabi]

I've been seeking for the reason of that WA for hours.
[cpp]#define MAX 100

struct coord
{
int x;
int y;
};

int cercaMax(vector<int>& a)
{
int aux = a[0];
for(int i = 1; i < a.size(); i++)
if(aux < a)
aux = a;
return aux;
}

int cercaMin(vector<int>& a)
{
int aux = a[0];
for(int i = 1; i < a.size(); i++)
if(aux > a)
aux = a;
return aux;
}

int main()
{
int tam, i, j, bleh;
int a[MAX][MAX];
coord aux;
vector<coord> uns;
vector<coord> tresos;
vector<int> auxVec, mins;
while(cin >> tam)
{
for(i = 0; i < tam; i++)
{
cin >> bleh;
for(j = tam - 1; j >= 0; j--)
{
a[j] = bleh % 10;
bleh = bleh / 10;
}
}
for(i = 0; i < tam; i++)
{
for(j = 0; j < tam; j++)
{
if(a[j] == 1)
{
aux.x = i;
aux.y = j;
uns.push_back(aux);
}
else if(a[j] == 3)
{
aux.x = i;
aux.y = j;
tresos.push_back(aux);
}
}
}
for(i = 0; i < uns.size(); i++)
{
for(j = 0; j < tresos.size(); j++)
{
auxVec.push_back(abs(uns.x - tresos[j].x) + abs(uns.y - tresos[j].y));
}
mins.push_back(cercaMin(auxVec));
auxVec.clear();
}
printf("%d\n", cercaMax(mins));
uns.clear();
tresos.clear();
mins.clear();
}
}[/cpp]
Does anyone have some other input or have a clue 'bout my problem?
Thanks

[Shabi]

i forget to say i've got AC finally

reason: input method

[Wei]

Code: Select all

    Cut after AC~~ ^^

[Antonio Ocampo]

Hi fellows

I have tried this problem but... I got several WA . Could someone give me a suggestion?

This is my 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,k,l,n;

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

         max=-1;

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

                for(k=0;k<n;++k)
                {
                  for(l=0;l<n;++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;
}

Thx in advance

[Sedefcho]

My Java program does basically what your C++
program does but gets ACC.

One difference I can see is that my program assumes
that there may be spaces, tabs or other symbols in the lines
in the input. I mean my program would behave OK even if
the input is like this one:

Code: Select all

4
1  2 2 3
212 3
22  13
3 2 12
  2  
1   2
3 3

The corresponding output is:

Code: Select all

3
1

I am not completely sure that this is the reason why your program
gets WA but it's worth trying to adjust your program so that it
behaves correctly on such inputs too.

Oh, and one second thing. I suggest you do not mix scanf with
gets in same program. Either 1) use a combination of gets and sscanf
or 2) use scanf only. Good luck !

[helloneo]

Code: Select all

cut

i modified my code.. and i still getting WA..
did i miss anything..?