## 298 - Race Tracks

Moderator: Board moderators

owl
New poster
Posts: 3
Joined: Thu Jun 20, 2002 6:13 am

### help! problems with 298!

[c]
#include <string.h>
#include <math.h>
#include <stdio.h>

int dp[30][30][7][7];
char ob[30][30];
int finalx, finaly;
int row, col;

void hops(int x, int y, int dx, int dy) {
int i, j;
int temp;
int newdx, newdy, newx, newy;
dp[x][y][dx][dy] = 50000;
if (ob[x][y])
return;
for (i = -1; i < 2; i++)
for (j = -1; j < 2; j++) {
newdx = i + dx;
newdy = j + dy;
newx = x + newdx - 3;
newy = y + newdy - 3;
if (newx < row && newx >= 0 && newy < col && newy >= 0 &&
(newdx < 7 && newdx >= 0) && (newdy < 7 && newdy >= 0) &&
!(newdx == dx && newdy == dy && newx == x && newy == y)) {
if (dp[newx][newy][newdx][newdy] == -1)
hops(newx, newy, newdx, newdy);
if (dp[newx][newy][newdx][newdy] != 50000) {
temp = dp[newx][newy][newdx][newdy] + 1;
dp[x][y][dx][dy] = (dp[x][y][dx][dy] > temp) ?
temp : dp[x][y][dx][dy];
}
}
}
}

int main() {
int counter;
int i, j, k, l, m;
char buf[1000];
int startx, starty;
int x1, y1, x2, y2;
gets(buf);
sscanf(buf, "%d", &counter);
for (m = 0; m < counter; m++) {
gets(buf);
sscanf(buf, "%d%d", &row, &col);
memset(ob, 0, sizeof(char) * 30 * 30);
memset(dp, -1, sizeof(int) * 30 * 30 * 7 * 7);
gets(buf);
sscanf(buf, "%d%d%d%d", &startx, &starty, &finalx, &finaly);
gets(buf);
sscanf(buf, "%d", &l);
for (k = 0; k < l; k++) {
gets(buf);
sscanf(buf, "%d%d%d%d", &x1, &x2, &y1, &y2);
for (i = x1; i <= x2; i++)
for(j = y1; j <= y2; j++)
ob[j] = 1;
}
for (i = 0; i < 7; i++)
for (j = 0; j < 7; j++)
dp[finalx][finaly][j] = 0;
if (!(startx == finalx && starty == finaly))
hops(startx, starty, 3, 3);
if (dp[startx][starty][3][3] == 50000)
printf("No solution.\n");
else
printf("Optimal solution takes %d hops.\n", dp[startx][starty][3][3]);
}
return 0;
}
[/c]
Have thought of many test cases and have passed all of them.
But still get wrong answer from judge.
Can anyone help?

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### help

Sorry, but I can't understand your program. Can you write your algorithm? Although I can advise you this things:

1. Check that speed always in range -3..3 (As I see you do it)

2. Check that coordinates always in range (0..X-1,0..Y-1)

owl
New poster
Posts: 3
Joined: Thu Jun 20, 2002 6:13 am
i have checked the bounds you have mentioned.
my algorithm is just dp with simple dfs.
and here are the test cases i have used.
correct answers are given for each test case.
10
5 5
4 0 4 4
1
1 4 2 4
5 5
4 0 4 4
1
1 2 2 4
3 3
0 0 2 2
2
1 1 0 2
0 2 1 1
5 5
0 4 4 4
1
1 4 2 3
30 30
0 0 29 29
1
1 4 2 3
30 30
0 0 29 29
0
30 30
0 0 0 1
0
6 6
0 0 5 5
1
5 5 5 5
7 7
0 0 0 4
0
7 7
0 0 0 0
1
0 6 0 6

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Here are the outputs for your inputs:
No solution.
Optimal solution takes 3 hops.
No solution.
Optimal solution takes 3 hops.
Optimal solution takes 12 hops.
Optimal solution takes 11 hops.
Optimal solution takes 1 hops.
No solution.
Optimal solution takes 3 hops.
Optimal solution takes 0 hops.
Hope can help~

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
My program write not
No solution.
Optimal solution takes 3 hops.
No solution.
Optimal solution takes 3 hops.
Optimal solution takes 12 hops.
Optimal solution takes 11 hops.
Optimal solution takes 1 hops.
No solution.
Optimal solution takes 3 hops.
No solution.
But the last test is wrong. In problem desription is written:
The start point will never be occupied.

owl
New poster
Posts: 3
Joined: Thu Jun 20, 2002 6:13 am

### Thanks everyone

Thanks!
but mine gives the same result as yours(any one of you except the last one).
so still don't know what's wrong!!!!

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
I think the word *occupied* means the position does not contain an obstacle, but does not mean it cannot be a starting position.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
A year and then some later...

Yeah, 10153EN is right.. It says:
The string 'No solution.' if there is no way the hopper can reach the finish point from the start point without hopping on an occupied square.
If you don't need to jump, you need not worry about hopping on an occupied square. My program didn't take that into account, so got WA. But after I added that little condition in, it was right.

Trickster
New poster
Posts: 6
Joined: Sat Sep 20, 2003 6:31 am
Location: Recife, Brazil

### 298 - Race Tracks

Hi everyone,

i
"There's a difference between knowing the path, and walking the path."

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

### 298 - Race Tracks

I try solve this problem and got WA many times.

I maked BFS with memorization and got a lot of WA!

This is my code:

Code: Select all

``````#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;

#define V(c) vector <c>
#define ALL(c) (c).begin(),(c).end()
#define FOR(i,v,n) for(int i=v,_n=n;i<_n;++i)
#define FORD(i,v,n) for(int i=(n-1),_v=v;i>=_v;--i)
#define REP(i,n) FOR(i,0,n)
#define REPD(i,n) FORD(i,0,n)
#define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define sz(c) (c).size()

#define arraySz(c) (sizeof(c)/sizeof(c[0]))

struct No {
int x,y,n,vx,vy;
No() {}
No(int _x, int _y, int _n, int _vx, int _vy) {
x=_x; y=_y; n=_n; vx=_vx, vy=_vy;
}
};

typedef vector<int> vi;
typedef vector<vi> vvi;

int X,Y;
int xs,ys,xe,ye;
vvi cenario;

struct cmp {
bool operator()(const No& n1, const No& n2) {
if (n1.n!=n2.n)
return n1.n>n2.n;
return ( abs(n1.x-xe) + abs(n1.y-ye) ) >
( abs(n2.x-xe) + abs(n2.y-ye) );
}
};

//int dx[] = {+1,+1,-1,-1};
//int dy[] = {+1,-1,+1,-1};
int dx[] = {+1,+1,-1,-1};
int dy[] = {+1,-1,+1,-1};

int memo[31][31][31][31];

void fill(vvi& a, int x1, int y1, int x2, int y2) {
if (y1>y2) swap(y1,y2);
if (x1>x2) swap(x1,x2);

for(int y=y1; y<=y2; y++)
for(int x=x1; x<=x2; x++)
a[y][x]=1;
}

int main( int argc, char* argv[] ) {

int ncases; cin>>ncases;
while(ncases--) {
cin>>X>>Y;

cenario = vvi(Y+1, vi(X+1, 0));
cin>>xs>>ys>>xe>>ye;

int p; cin>>p;
while(p--) {
int x1,y1,x2,y2; cin>>x1>>x2>>y1>>y2;
fill(cenario,x1,y1,x2,y2);
}

//REP(i,Y) { REP(j,X) cout<<cenario[i][j]; cout<<endl; } cout<<endl;

//priority_queue<No, vector<No>, cmp > fila;
queue<No> fila;
fila.push(No(xs,ys,0,0,0));

// limpando matriz de memorizacao
memset(memo,0,sizeof(memo));

int melhor=-1;
while(!fila.empty()) {
int x=fila.front().x;
int y=fila.front().y;
int n=fila.front().n;
int vx=fila.front().vx;
int vy=fila.front().vy;
fila.pop();

//cout<<"x:"<<x<<" y:"<<y<<" n:"<<n<<" vx:"<<vx<<" vy:"<<vy<<endl;

memo[y][x][vy][vx]=1;
if (xe==x && ye==y) {
melhor=n;
break;
}

FOR(_vx, vx-1, vx+2) {
// FOR(_vy, vy-1, vy+2) {
int _vy = vy;
REP(i,arraySz(dx)) {
int _x = dx[i] * _vx + x, _y = dy[i] * _vy + y;
if (_x < 0 || _x >= X || _y < 0 || _y >= Y ||
_vx < 0 || _vy < 0 || cenario[_y][_x] || memo[_y][_x][_vy][_vx])
continue;

memo[_y][_x][_vy][_vx]=1;
fila.push(No(_x,_y,n+1,_vx,_vy));
}
}

FOR(_vy, vy-1, vy+2) {
int _vx = vx;
REP(i,arraySz(dx)) {
int _x = dx[i] * _vx + x, _y = dy[i] * _vy + y;
if (_x < 0 || _x >= X || _y < 0 || _y >= Y ||
_vx < 0 || _vy < 0 || cenario[_y][_x] || memo[_y][_x][_vy][_vx])
continue;

memo[_y][_x][_vy][_vx]=1;
fila.push(No(_x,_y,n+1,_vx,_vy));
}
}

}

if (melhor==-1) {
cout<<"No solution."<<endl;
}
else {
cout<<"Optimal solution takes "<<melhor<<" hops."<<endl;
}
}
return 0;
}
``````
For this input:

Code: Select all

``````4
5 5
4 0 4 4
1
1 4 2 3
3 3
0 0 2 2
2
1 1 0 2
0 2 1 1
5 5
4 0 4 0
1
1 4 2 3
5 5
4 0 4 1
1
1 4 2 3``````
I get:

Code: Select all

``````Optimal solution takes 7 hops.
No solution.
Optimal solution takes 0 hops.
Optimal solution takes 1 hops.
``````

Davi2006
New poster
Posts: 2
Joined: Fri May 05, 2006 12:33 pm

This is my code. This code pass all this test but it always have a WA, can somebody help me?

#include <iostream>
using namespace std;

int terreno[30][30][7][7];
int MaxX,MaxY,PosFX,PosFY;
int aceleracion[3]={-1,0,1};

int mejor_camino(int PosIX,int PosIY,int vX,int vY){
int i,j,auxR;
int mejor_c=-1;
if ((PosIX==PosFX) && (PosIY==PosFY)){
if (terreno[PosIX][PosIY][vX+3][vY+3]==-1) return -1; else return 0;
}else if(terreno[PosIX][PosIY][vX+3][vY+3]==-1){
return -1;
}else if(terreno[PosIX][PosIY][vX+3][vY+3]>0){
return terreno[PosIX][PosIY][vX+3][vY+3];
}else{
terreno[PosIX][PosIY][vX+3][vY+3]=-1;
for(i=0;i<3;i++){
if ((vX+aceleracion[i]>=-3) && (vX+aceleracion[i]<=3) && (PosIX+vX+aceleracion[i]>=0) && (PosIX+vX+aceleracion[i]<MaxX)){
for(j=0;j<3;j++){
if ((vY+aceleracion[j]>=-3) && (vY+aceleracion[j]<=3) && (PosIY+vY+aceleracion[j]>=0) && (PosIY+vY+aceleracion[j]<MaxY)){
auxR=mejor_camino(PosIX+vX+aceleracion[i],PosIY+vY+aceleracion[j],vX+aceleracion[i],vY+aceleracion[j]);
if ((auxR>-1) && ((mejor_c==-1)||(auxR<mejor_c))) mejor_c=auxR+1;
}
}
}
}
terreno[PosIX][PosIY][vX+3][vY+3]=mejor_c;
return mejor_c;
}
}

int main()
{
int N,i,j,k,l,m,n,PosIX,PosIY,numObstaculos,X1,X2,Y1,Y2;
cin >> N;
for (i=0;i<N;i++){
cin >> MaxX >> MaxY >> PosIX >> PosIY >> PosFX >> PosFY >> numObstaculos;

for (j=0;j<MaxX;j++)
for (k=0;k<MaxY;k++)
for (l=0;l<7;l++)
for (m=0;m<7;m++)
terreno[j][k][l][m]=0;

for (n=0;n<numObstaculos;n++){
cin >> X1 >> X2 >> Y1 >> Y2;
for (j=X1;j<=X2;j++)
for (k=Y1;k<=Y2;k++)
for (l=0;l<7;l++)
for (m=0;m<7;m++)
terreno[j][k][l][m]=-1;
}
if ((m=mejor_camino(PosIX,PosIY,0,0))>-1){
cout << "Optimal solution takes " << m << " hops.";
}else{
cout << "No solution.";
}
if (i<N-1)cout << endl;
}
}

Davi2006
New poster
Posts: 2
Joined: Fri May 05, 2006 12:33 pm

### 298

This is my code. This code pass all test that I have found in this forum but it always have a WA, can somebody help me?

#include <iostream>
using namespace std;

int terreno[30][30][7][7];
int MaxX,MaxY,PosFX,PosFY;
int aceleracion[3]={-1,0,1};

int mejor_camino(int PosIX,int PosIY,int vX,int vY){
int i,j,auxR;
int mejor_c=-1;
if ((PosIX==PosFX) && (PosIY==PosFY)){
if (terreno[PosIX][PosIY][vX+3][vY+3]==-1) return -1; else return 0;
}else if(terreno[PosIX][PosIY][vX+3][vY+3]==-1){
return -1;
}else if(terreno[PosIX][PosIY][vX+3][vY+3]>0){
return terreno[PosIX][PosIY][vX+3][vY+3];
}else{
terreno[PosIX][PosIY][vX+3][vY+3]=-1;
for(i=0;i<3;i++){
if ((vX+aceleracion>=-3) && (vX+aceleracion<=3) && (PosIX+vX+aceleracion>=0) && (PosIX+vX+aceleracion<MaxX)){
for(j=0;j<3;j++){
if ((vY+aceleracion[j]>=-3) && (vY+aceleracion[j]<=3) && (PosIY+vY+aceleracion[j]>=0) && (PosIY+vY+aceleracion[j]<MaxY)){
auxR=mejor_camino(PosIX+vX+aceleracion,PosIY+vY+aceleracion[j],vX+aceleracion,vY+aceleracion[j]);
if ((auxR>-1) && ((mejor_c==-1)||(auxR<mejor_c))) mejor_c=auxR+1;
}
}
}
}
terreno[PosIX][PosIY][vX+3][vY+3]=mejor_c;
return mejor_c;
}
}

int main()
{
int N,i,j,k,l,m,n,PosIX,PosIY,numObstaculos,X1,X2,Y1,Y2;
cin >> N;
for (i=0;i<N;i++){
cin >> MaxX >> MaxY >> PosIX >> PosIY >> PosFX >> PosFY >> numObstaculos;

for (j=0;j<MaxX;j++)
for (k=0;k<MaxY;k++)
for (l=0;l<7;l++)
for (m=0;m<7;m++)
terreno[j][k][l][m]=0;

for (n=0;n<numObstaculos;n++){
cin >> X1 >> X2 >> Y1 >> Y2;
for (j=X1;j<=X2;j++)
for (k=Y1;k<=Y2;k++)
for (l=0;l<7;l++)
for (m=0;m<7;m++)
terreno[j][k][l][m]=-1;
}
if ((m=mejor_camino(PosIX,PosIY,0,0))>-1){
cout << "Optimal solution takes " << m << " hops.";
}else{
cout << "No solution.";
}
if (i<N-1)cout << endl;
}
}