## 556 - Amazing

Moderator: Board moderators

rickyok
New poster
Posts: 8
Joined: Mon Jun 10, 2002 5:17 pm
Location: Jakarta, Indonesia

### 556 - Amazing

Seems ok

[c]

#include <stdio.h>

#define MAXX 100
#define MAXY 100

int map[MAXX][MAXY];
int cnt[MAXX][MAXY];
int mx , my;
int ax , ay;
int cx , cy;

void get_data(int x , int y) {
int xx, yy;
char temp[100];
for (yy = 0 ; yy < y ; yy++) {
gets(temp);
for(xx = 0 ; xx < x ; xx++) {
map[xx][yy] = temp[xx] - '0';
cnt[xx][yy] = 0;
}
}
}

void change_dir(void) {
if (ax == 0) {
ax = ay ; ay = 0;
}
else if (ay == 0) {
ay = -ax; ax = 0;
}
}

int validxy(int x , int y) {
if (x < 0 || x >= mx) return 0;
if (y < 0 || y >= my) return 0;
if (map[x][y] == 1) return 0;
return 1;
}

int check_right(int x , int y) {
int rx , ry;
if (y == 0) {
ry = x ; rx = 0;
}
else if (x == 0) {
rx = -y ; ry = 0;
}
if (validxy(cx+rx,cy+ry)) return 1;
else return 0;
}

void move_right(void) {
if (ay == 0) {
ay = ax ; ax = 0;
}
else if (ax == 0) {
ax = -ay ; ay = 0;
}
}

void gen_move(void) {
while (cx != 0 || (cy != my-1) || cnt[cx][cy] != 1) {
if (check_right(ax , ay)) {
move_right();
}
else {
while (!validxy(cx + ax , cy + ay)) {
change_dir();
}
}
cnt[cx][cy]++;
cx += ax; cy += ay;
}
}

void cetak_hasil(void) {
int nol , satu, dua , tiga , empat;
int a, b;
nol = satu = dua = tiga = empat = 0;
for (a = 0 ; a < mx ; a++) {
for (b = 0 ; b < my ; b++) {
if (!map[a])
switch(cnt[a]) {
case 0 : nol++ ; break;
case 1 : satu++ ; break;
case 2 : dua++ ; break;
case 3 : tiga++ ; break;
case 4 : empat++ ; break;
}
}
}
printf("%3d%3d%3d%3d%3d\n",nol,satu,dua,tiga,empat);
}

void main() {
int xx ,yy;
while (scanf("%d %d" , &my , &mx) == 2) {
if ((mx && my) == 0) break;
fflush(stdin);
get_data(mx,my);
cx = 0;
cy = my-1;
ax = 1;
ay = 0;
gen_move();
cetak_hasil();
}
}

@END_OF_SOURCE_CODE
[/c]
"Why you care about small things? World very simple place.
World only have two things: Things you can eat and things you no can eat." - Quina

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Hello, ... looks to me your problem is related to how you scan the input.

Try to change the first few lines of your main() like this:

[c]
void main() {
int xx ,yy;
static char sss[256];
while (1) {
gets(sss);
sscanf(sss, "%d %d" , &my , &mx);
if ((mx && my) == 0) break;
get_data(mx,my);
cx = 0;
cy = my-1;
ax = 1;
ay = 0;
gen_move();
cetak_hasil();
}
}
[/c]

-turuthok-

rickyok
New poster
Posts: 8
Joined: Mon Jun 10, 2002 5:17 pm
Location: Jakarta, Indonesia
Thank you turuthok for your replies
But i have found the problem it is right here :

[c]void get_data(int x , int y) {
int xx, yy;
char temp[100];
for (yy = 0 ; yy < y ; yy++) {
gets(temp);
for(xx = 0 ; xx < x ; xx++) {
map[xx][yy] = temp[xx] - '0';
cnt[xx][yy] = 0;
}
}
}
[/c]

Should be written like this :

[c]void get_data(int x , int y) {
int xx, yy;
char temp[100];
for (yy = 0 ; yy < y ; yy++) {
scanf("%s" , temp);
for(xx = 0 ; xx < x ; xx++) {
map[xx][yy] = temp[xx] - '0';
cnt[xx][yy] = 0;
}
}
}
[/c]
"Why you care about small things? World very simple place.
World only have two things: Things you can eat and things you no can eat." - Quina

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
rickyyok, ... I'm sure that would do it, too.

The problem is the usage of gets() and scanf() in the same program. I'm not sure if they can live together ... Basically, we got to know the behavior of those input functions.

Of course if the input file format is simple, one can simply use one of them. But, if the input file becomes a little bit more complicated, try to use gets() and sscanf(), ... pretty handy ...

Say my hi to fellow Indonesians in this forum

-turuthok-

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 556 can anyone explain to me please??

I don't understand what this statemeant means:
The robot then moved through the maze, keeping a wall on its right at all times. If it can not proceed, it will turn left until it can proceed.

As I understand, in the sample input, the robot will walk this way,
(^ > V < represents the direction of robot N E S W)

01010
01010
>0000 go forward

01010
01010
0000> turn left

01010
01010
0000^ go forward

0101^ turn left
01010
00000

0101< turn left
01010
00000

0101V go forward
01010
00000

01010
01010
0000V turn left

01010
01010
0000> repeat previous step and got trapped in rightmost column??

Can anyone tell me what's wrong??
Thanks a lot!
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
When the robot is here:

01010
0101V
00000

it has a wall to its right. One step later, there is no wall to the right, so in order for the robot to "maintain contact with the wall to its right" it must make a right turn, regaining contact with the wall. The state is then:

01010
01010
000<0

So if we have a maze like this:

0>0000
011010
011010
000000

the robot will go around in a square, and never go to the right part of the maze.

Hope this helps.

Asma50
New poster
Posts: 1
Joined: Mon Aug 06, 2012 9:01 pm

### Re: 556 can anyone explain to me please??

Convey (my teachings) to the people even if it were a single sentence. (Sahih Bukhari, Volume 4, Book 56, Number 667) http://islamicsharing.com

ljacs
New poster
Posts: 5
Joined: Wed Sep 05, 2012 5:53 am

### 556 - Why WA? (Amazing)

Code: Select all

``````Accepted.
``````
Hello there! This is my code for problem n. 556 (Amazing).
I know I might not have done it the smartest way around but I've tested several cases and even critical inputs and the outputs are correct.
Last edited by ljacs on Wed Sep 05, 2012 11:03 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 556 - Why WA? (Amazing)

Don't double post.

Doesn't match the sample I/O. You need to initialize valores[] before the first printf.
https://ideone.com/sB49u
Check input and AC output for thousands of problems on uDebug!

ljacs
New poster
Posts: 5
Joined: Wed Sep 05, 2012 5:53 am

### Re: 556 - Why WA? (Amazing)

Oh, you're right. I don't know why but the IDE I use would give me the correct output O.o
Anyway, thanks, I got accepted. And sorry for the double post, I did it because I realized after a while I did not post at the right place. It's deleted already anyways.
Thank you

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 556 - Why WA? (Amazing)

Some systems will initialize variables to zero for you, but never assume that all systems will.
Check input and AC output for thousands of problems on uDebug!

csantos
New poster
Posts: 2
Joined: Tue Feb 11, 2014 12:03 am

### 556 - Need clarification

So after re-reading the problem 556 "Amazing", I still don't get how the robot is supposed to explore the environment. By (manually) following the algorithm described in the problem on the sample map, I would run into an infinite loop at the rightmost vertical corridor. Let "x" be the "trail" left by the robot in an environment, this would be its trajectory according to the problem description:

01010
01010
x0000
(four steps later to the right...)
01010
01010
xxxxx
(turns left and two steps forward)
0101x
0101x
xxxxx
(turns left twice and two steps forward)
0101x
0101X
xxxxX
at this point, by turning left, the robot will be facing the rightmost wall (just like it was when it first reached the lower, rightmost corner), and the loop will repeat. What did I get wrong here?

Thanks

csantos
New poster
Posts: 2
Joined: Tue Feb 11, 2014 12:03 am

### Re: 556 - Need clarification

Got it. Turns out the spec is really not very clear. Just forget the "If it can not proceed, it will turn left until it can proceed.". The spec can be summarized as: "make the robot contour the map by always having a wall at its right side".

mratan16
New poster
Posts: 21
Joined: Fri May 16, 2014 12:36 am

### 556 - Amazing Help

cannot seem to find my mistake in the code. Can anyone help?

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

vector<vector<int> > grid;
vector<vector<int> >visited;
int h,w;

struct pos{
int x,y; // WHere y is height and x width in the format [y][x]
};

void mov(int &dir, pos &cur)
{
// Move based on direction being faced.
// 1=moving right
// 2= moving up
// 3= moving left
// 4=moving down
switch(dir) //Conditions: 1. Has to be possible 2. Right side is wall
{
case 1: //Right
{
if( cur.x+1<=w-1 && grid[cur.y][cur.x+1]!=1 && (cur.y==h-1 ||grid[cur.x][cur.y+1]==1) )
{
cur.x++;
visited[cur.y][cur.x]++;

}
else
{
dir++;
}
break;
}

case 2: //UP
{
if(cur.y-1>=0 && grid[cur.y-1][cur.x]!=1 && (cur.x==w-1 || grid[cur.x+1][cur.y]==1) )
{
cur.y--;
visited[cur.y][cur.x]++;
}
else
{
dir++;
}
break;
}

case 3:  //Left
{
/*
cout << "case:3" << endl;
cout << cur.x-1 << " " << grid[cur.y][cur.x-1] << " " <<endl;
cout << grid[cur.y][cur.x]<< endl;
*/

if(cur.x-1>=0 && grid[cur.y][cur.x-1]!=1 && (cur.y==0 || grid[cur.x][cur.y-1]==1))
{
cur.x--;
visited[cur.y][cur.x]++;
}
else
{
dir++;
}
break;
}

case 4: //Down
{

cout << "case:4" << endl;
cout << cur.y+1 << " " << grid[cur.y+1][cur.x] << " " <<endl;
cout << grid[cur.x-1][cur.y] << " ";

if(cur.y+1<=h-1 && grid[cur.y+1][cur.x]!=1 && (cur.x==0 || grid[cur.x-1][cur.y]==1) )
{
cur.y++;
visited[cur.y][cur.x]++;
}
else
{
dir=1;
}
break;
}

}
}

int main()
{

while(cin>>h>>w)
{
grid.resize(h);
visited.resize(h);
for(int i=0; i<h; ++i)
{
grid[i].resize(w);
visited[i].resize(w);
}

for(int i=0; i<h; ++i)
{
string a;
cin>>a;
for(int j=0; j<w; ++j)
{
grid[i][j]=a[j]-'0';
}
}
/*
cout << endl;
for(int i=0; i<h;++i){
for(int j=0; j<w; ++j)
{
cout << grid[i][j];
}
cout << endl;
}
*/

pos start;
start.x=0;
start.y=h-1;

pos cur;
cur.y=start.y;
cur.x=start.x;

int dir=1;
int no_of_visits[5]={0};
cout << cur.y <<" " << cur.x << " " << dir<< endl;

while(true)
{

mov(dir, cur);
cout << cur.y <<" " << cur.x << " " << dir<< endl;

if(cur.x==start.x && cur.y==start.y)
{
break;
}
}

for(int i=0; i<h; ++i)
{
for(int j=0; j<w;  ++j)
{
no_of_visits[visited[i][j]-1]++;
}
}
for(int i=0; i<5; ++i)
{
cout <<no_of_visits[i]<< " ";
}
cout << endl;

}

}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 556 - Amazing Help

Try running your code on the sample input.
Check input and AC output for thousands of problems on uDebug!