10102 - The path in the colored field

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

wenzhi cai
New poster
Posts: 9
Joined: Sat Jun 29, 2002 10:59 am
Location: china
Contact:

10102 - The path in the colored field

Post by wenzhi cai » Fri Jul 19, 2002 4:01 pm

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

AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

Post by AlexandreN » Mon Aug 26, 2002 9:39 pm

I was wrong. :oops:
Last edited by AlexandreN on Thu Aug 29, 2002 1:29 pm, edited 1 time in total.

AlexandreN
New poster
Posts: 27
Joined: Sun Jul 07, 2002 6:46 pm
Location: Campina Grande - Brazil
Contact:

Post by AlexandreN » Thu Aug 29, 2002 1:29 pm

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

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 » Fri Oct 04, 2002 5:36 pm

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
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Sat Oct 05, 2002 1:56 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Aug 04, 2003 6:37 am

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Aug 04, 2003 12:43 pm

Nevermind.. typo..

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani » Wed Aug 06, 2003 7:14 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Aug 06, 2003 12:53 pm

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

Shabi
New poster
Posts: 2
Joined: Thu Jul 01, 2004 8:20 am

10102 WA

Post by Shabi » Thu Jul 01, 2004 8:25 am

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
New poster
Posts: 2
Joined: Thu Jul 01, 2004 8:20 am

Post by Shabi » Thu Jul 01, 2004 5:13 pm

i forget to say i've got AC finally

reason: input method

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

10102...

Post by Wei » Wed Mar 23, 2005 2:37 pm

Code: Select all

    Cut after AC~~ ^^

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Thu Jun 23, 2005 4:28 am

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 :wink:

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Aug 31, 2005 12:02 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

wa..

Post by helloneo » Wed Aug 31, 2005 4:36 pm

Code: Select all

cut
i modified my code.. and i still getting WA..
did i miss anything..?
Last edited by helloneo on Wed Aug 31, 2005 5:35 pm, edited 1 time in total.

Post Reply

Return to “Volume 101 (10100-10199)”