10500 - Robot maps

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier »

No, the number of movements is the number of times the robot moved from one cell to an other.
Not AC yet Image AC at last Image

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by 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
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by 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
Not AC yet Image AC at last Image

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

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

Code: Select all

got ac thanks to all..
just stupid mistakes.
 :P  after exam,head is blocked
Thanks to all for help.
:oops: :oops: [/b]
Last edited by anupam on Tue Jul 22, 2003 6:23 pm, edited 2 times in total.
"Everything should be made simple, but not always simpler"

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by 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
Kalo mau kaya, buat apa sekolah?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by 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
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by 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...
:-?
Sajid Online: www.sajidonline.com

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

WA Help

Post by 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
...I was born to code...

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

accepted but P.E., problem 10500

Post by 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
New poster
Posts: 34
Joined: Mon Nov 17, 2003 10:41 am

Re: accepted but P.E., problem 10500

Post by LPH »

WR wrote: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?
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

P.E. problem 10500

Post by 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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by 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
New poster
Posts: 7
Joined: Tue Jan 21, 2003 4:52 am
Location: Hong Kong
Contact:

Post by 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
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by 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*
*

Post Reply

Return to “Volume 105 (10500-10599)”