10500 - Robot maps

[bery olivier]

No, the number of movements is the number of times the robot moved from one cell to an other.

[htl]

Then why the first example of the prob is 7?? My prog calculated it as 8... Could someone tell me where I'm wrong??

[bery olivier]

Here is how it works (sorry I can't make ascii graphics here):

| ? | X | 0 | 1 | X |
| ? | X | 0 | 2 | X |
| X | 7 | X | 3 | X |
| X | 6 | 5 | 4 | X |
| ? | X | X | X | ? |

The movements are numbers from 1 to 7. That's why the answer is 7.
The red '0' is the initial robot postition. So it doesn't need to move to reach that destination.
The green '0' is unreachable because the robot selects its movements clockwise starting from north. So It reaches the cell '7'. It will then unable to move.

Hope that it'll help.

it can not move any further because all the cells around it are occupied or have already been visited

[Larry]

Can someone post some inputs? I keep getting WA and I can't figure out why..

[anupam]

Hello all.
I read all the discussions and try to get ac but still wa.
will any1 please help???
Here is my code....

Code: Select all

got ac thanks to all..
just stupid mistakes.
 :P  after exam,head is blocked

Thanks to all for help.
[/b]

[titid_gede]

i didnt read all lines, but you print function is not correct. how can you generalize all input has 5 coloums ? and this is not DFS problem. just simulation. you dont need to backtrack when there is no way to go. hope it can help.

regards,

titid

[UFP2161]

From problem description:

The map must be a correct one, which means the initial position of the robot must be always an empty cell.

So, did they fix the problem with the '0' starting position, 'cause I just sent a solution (P.E. prolly need a extra newline at the EOF or something) w/o ever setting the starting position to '0' before or after the simulation.

[Sajid]

Can anyone tell me what is the north direction for this problem?
I guess its the upward direction ([i-1][j]).

I simulate the program using the given order, I think ROBOT can go only 1 path (direction), never come back. on the way, it defines the states of the blocks of the four direction from it's current position.

If the source is on the 'X' mark state (according to Adriel), I marked it 'X' and also defined the states of its neighbour in four direction.. thats it..

but getting WA...

[aakash_mandhar]

Can anyone tell me what is wrong with the code..
Thx in advance...
[cpp]

# include<iostream.h>

int a[10][10];
int b[10][10];
int m,n,i,j;
int x,y,x1;
int nom;
char ch;

int main()
{
while(1)
{
cin>>m>>n;
if(m==0 && n==0) break;
nom=0;
cin>>x>>y;
x--;y--;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
cin>>ch;
if(ch=='X') {a[j]=1;b[j]=-2;}
if(ch=='0') {a[j]=0;b[j]=-2;}
}
}
b[x][y]=0;
a[x][y]=0;
if(x>0 && a[x-1][y]==1) {b[x-1][y]=1;}
if(y<n-1 && a[x][y+1]==1) {b[x][y+1]=1;}
if(x<m-1 && a[x+1][y]==1 ) {b[x+1][y]=1;}
if(y>0 && a[x][y-1]==1) {b[x][y-1]=1;}


while(1)
{
if(x>0 && a[x-1][y]==0 && b[x-1][y]==-2)
{
x--;b[x][y]=0;nom++;
if(x>0 && a[x-1][y]==1) {b[x-1][y]=1;}
if(y<n-1 && a[x][y+1]==1) {b[x][y+1]=1;}
if(x<m-1 && a[x+1][y]==1 ) {b[x+1][y]=1;}
if(y>0 && a[x][y-1]==1) {b[x][y-1]=1;}

}
//else
//if(x>0 && a[x-1][y]==1) {b[x-1][y]=1;}
else
if(y<n-1 && a[x][y+1]==0 && b[x][y+1]==-2)
{
y++;b[x][y]=0;nom++;
if(x>0 && a[x-1][y]==1) {b[x-1][y]=1;}
if(y<n-1 && a[x][y+1]==1) {b[x][y+1]=1;}
if(x<m-1 && a[x+1][y]==1 ) {b[x+1][y]=1;}
if(y>0 && a[x][y-1]==1) {b[x][y-1]=1;}

}
//else
//if(y<n-1 && a[x][y+1]==1) {b[x][y+1]=0;}
else
if(x<m-1 && a[x+1][y]==0 && b[x+1][y]==-2)
{
x++;b[x][y]=0;nom++;
if(x>0 && a[x-1][y]==1) {b[x-1][y]=1;}
if(y<n-1 && a[x][y+1]==1) {b[x][y+1]=1;}
if(x<m-1 && a[x+1][y]==1 ) {b[x+1][y]=1;}
if(y>0 && a[x][y-1]==1) {b[x][y-1]=1;}

}
//else
//if(x<m-1 && a[x+1][y]==1 ) {b[x+1][y]=0;}
else
if(y>0 && a[x][y-1]==0 && b[x][y-1]==-2)
{
y--;b[x][y]=0;nom++;
if(x>0 && a[x-1][y]==1) {b[x-1][y]=1;}
if(y<n-1 && a[x][y+1]==1) {b[x][y+1]=1;}
if(x<m-1 && a[x+1][y]==1 ) {b[x+1][y]=1;}
if(y>0 && a[x][y-1]==1) {b[x][y-1]=1;}

}
//else
//if(y>0 && a[x][y-1]==1) {b[x][y-1]=0;}
else
break;
}

for(i=0;i<m;i++)
{
for(x1=0;x1<=4*n;x1++)
{
if(x1%4==0) cout<<"|";
else cout<<"-";
}
cout<<"\n";
for(j=0;j<n;j++)
{
cout<<"| ";
if(b[j]==-2) cout<<"? ";
if(b[j]==0) cout<<"0 ";
if(b[j]==1) cout<<"X ";
}
cout<<"|\n";
}
for(x1=0;x1<=4*n;x1++)
{
if(x1%4==0) cout<<"|";
else cout<<"-";
}
cout<<"\n\nNUMBER OF MOVEMENTS: "<<nom<<"\n\n";
}
return 1;
}


[/cpp]

I got really frustrated coz this is an easy problem

[WR]

What could be the reason for a presentation error in this problem?

There should be one blank line before

writeln(output,'NUMBER OF MOVEMENTS: ',moves);

and another after that. Right?

Any suggestions?

[LPH]

What could be the reason for a presentation error in this problem?

There should be one blank line before

writeln(output,'NUMBER OF MOVEMENTS: ',moves);

and another after that. Right?

Any suggestions?

the blank line after "NUMBER OF MOVEMENTS:" should be the first blank line in the next test case.

by the way, i think i've tried every possible situation (included the problem of 'X' at the source) but still getting WA. are there any other tricks of this problem?

[WR]

Well I've tried that, still P.E.

But as the program has been accepted, I'll quit worrying.

I don't think there's any tricky input. Before moving just scan
the neighbouring cells, remeber them and move, if possible.

[minskcity]

Can anybody tell me where North/East are in this problem?
or find a mistake in my code?
[cpp]#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector < string > ans;
vector < string > in;
long m, n, x, y, a;
bool flag;

int main(){
while(cin >> n >> m >> x >> y && m + n){
x--; y--;
in.resize(n);
ans.resize(n);
for(long i = 0; i < n; i++){
in.resize(m);
for(long j = 0; j < m; j++) cin >> in[j];
}
for(long i = 0; i < n; i++) ans = "??????????????????";
flag = true;
a = -1;

while(flag){
a++;
flag = false;
in[x][y] = 'v';
ans[x][y] = '0';
if(x - 1 >= 0) ans[x - 1][y] = in[x - 1][y];
if(x + 1 < m) ans[x + 1][y] = in[x + 1][y];
if(y - 1 >= 0) ans[x][y - 1] = in[x][y - 1];
if(y + 1 < m) ans[x][y + 1] = in[x][y + 1];

if(x - 1 >= 0 && in[x - 1][y] == '0'){
x--;
flag = true;
continue;
}
if(y + 1 < m && in[x][y + 1] == '0'){
y++;
flag = true;
continue;
}
if(x + 1 < m && in[x + 1][y] == '0'){
x++;
flag = true;
continue;
}
if(y - 1 >= 0 && in[x][y - 1] == '0'){
y--;
flag = true;
continue;
}
}

cout << '|';
for(long i = 0; i < m; i++) cout << "---|";
cout << endl;
for(long i = 0; i < n; i++){
cout << '|';
for(long j = 0; j < m; j++) cout << ' ' << (ans[j] != 'v' ? ans[j] : '0') << " |";
cout << endl;
cout << '|';
for(long j = 0; j < m; j++) cout << "---|";
cout << endl;
}
cout << "\nNUMBER OF MOVEMENTS: " << a << "\n\n";
}

return 0;
}[/cpp]

[TWEmp]

I got WA either but I got every problem stated here solved, and even eliminated some more bugs of my own. Would you all mind providing some extreme test cases for me...?

[WR]

I'm not sure where I got those data, but perhaps they help. My program still gets a presentation error, though. End of line and newlines are marked by a star (*) in the sample output. May be somebody knows why that still is not ok.

input:

Code: Select all

5 5
1 3
X X 0 0 X
X X 0 0 X
X 0 X 0 X
X 0 0 0 X
X X X X X
5 5
1 1
0 0 X X X
X X 0 0 X
X 0 0 0 X
X 0 0 0 X
X X X X X
10 10
5 5
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X 0 X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
10 10
5 5
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 1
1 1
0
1 5
1 1
0 0 0 0 0
5 1
1 1
0
0
0
0
0
0 0

output:

Code: Select all

|---|---|---|---|---|*
|  ?|  X|  0|  0|  X|*
|---|---|---|---|---|*
|  ?|  X|  0|  0|  X|*
|---|---|---|---|---|*
|  X|  0|  X|  0|  X|*
|---|---|---|---|---|*
|  X|  0|  0|  0|  X|*
|---|---|---|---|---|*
|  ?|  X|  X|  X|  ?|*
|---|---|---|---|---|*
*
NUMBER OF MOVEMENTS: 7*
*
*
|---|---|---|---|---|*
|  0|  0|  X|  ?|  ?|*
|---|---|---|---|---|*
|  X|  X|  ?|  ?|  ?|*
|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|*
*
NUMBER OF MOVEMENTS: 1*
*
*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  X|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  X|  0|  X|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  X|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|  ?|*
|---|---|---|---|---|---|---|---|---|---|*
*
NUMBER OF MOVEMENTS: 0*
*
*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|*
|---|---|---|---|---|---|---|---|---|---|*
*
NUMBER OF MOVEMENTS: 99*
*
*
|---|*
|  0|*
|---|*
*
NUMBER OF MOVEMENTS: 0*
*
*
|---|---|---|---|---|*
|  0|  0|  0|  0|  0|*
|---|---|---|---|---|*
*
NUMBER OF MOVEMENTS: 4*
*
*
|---|*
|  0|*
|---|*
|  0|*
|---|*
|  0|*
|---|*
|  0|*
|---|*
|  0|*
|---|*
*
NUMBER OF MOVEMENTS: 4*
*