## 10102 - The path in the colored field

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

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:
I was wrong.
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:
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
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
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?
Could the numbers in the table be separated by spaces or blank lines?

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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:
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:
Nevermind.. typo..
Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 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:
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

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
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...

Code: Select all

``````    Cut after AC~~ ^^
``````
Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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;
}
``````
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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..

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.