298

owl · Post by **owl** » Thu Jun 20, 2002 6:19 am

[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 · Post by **Revenger** » Thu Jun 20, 2002 11:34 am

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)

May be this help you

owl · Post by **owl** » Thu Jun 20, 2002 11:39 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 · Post by **10153EN** » Thu Jun 20, 2002 12:51 pm

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 · Post by **Revenger** » Thu Jun 20, 2002 2:09 pm

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 · Post by **owl** » Thu Jun 20, 2002 5:22 pm

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 · Post by **10153EN** » Thu Jun 20, 2002 7:24 pm

I think the word *occupied* means the position does not contain an obstacle, but does not mean it cannot be a starting position.

UFP2161 · Post by **UFP2161** » Sun Aug 31, 2003 3:41 am

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 · Post by **Trickster** » Sat Dec 27, 2003 4:20 pm

Hi everyone,

i

wanderley2k · Post by **wanderley2k** » Thu Aug 25, 2005 10:15 pm

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

I get:

Code: Select all

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

Thanks to advince!

[/code]

Davi2006 · Post by **Davi2006** » Fri May 05, 2006 12:38 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 · Post by **Davi2006** » Tue May 30, 2006 10:05 am

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;
}
}

OJ Board

298 - Race Tracks

help! problems with 298!

help

Thanks everyone

298 - Race Tracks

298 - Race Tracks

Wrong Answer