556 - Amazing

[rickyok]

Please help, I don't know what's wrong with this code
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]

[turuthok]

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]

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]

[turuthok]

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-

[..]

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!

[Per]

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]

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]

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.
Still, I'm getting wrong answer for this code. Could anyone please help me with that? Much appreciated.

[brianfry713]

Don't double post.

Doesn't match the sample I/O. You need to initialize valores[] before the first printf.
https://ideone.com/sB49u

[ljacs]

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]

Some systems will initialize variables to zero for you, but never assume that all systems will.

[csantos]

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]

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]

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]

Try running your code on the sample input.