298 - Race Tracks
Moderator: Board moderators
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?
#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?
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)
May be this help you
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

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.
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
Here are the outputs for your inputs:
Hope can help~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.
My program write not
But the last test is wrong. In problem desription is written: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.
The start point will never be occupied.
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!!!!
but mine gives the same result as yours(any one of you except the last one).
so still don't know what's wrong!!!!
A year and then some later...
Yeah, 10153EN is right.. It says:
Yeah, 10153EN is right.. It says:
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.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.
298 - Race Tracks
Hi everyone,
i
i
"There's a difference between knowing the path, and walking the path."
-
- 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:
For this input:
I get:
Thanks to advince!
[/code]
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;
}
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
Code: Select all
Optimal solution takes 7 hops.
No solution.
Optimal solution takes 0 hops.
Optimal solution takes 1 hops.

Wrong Answer
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;
}
}
#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;
}
}
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;
}
}
#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;
}
}