314 - Robot

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

Moderator: Board moderators

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

314 - Robot

Post by zobayer » Sun Jul 04, 2010 7:35 pm

Hello, I am getting wrong answer for this problem. Here is my solution, please help me to find the bug.

Code: Select all

Accepted
Thanks in advance.
You should not always say what you know, but you should always know what you say.

lucasbueno
New poster
Posts: 1
Joined: Wed Dec 22, 2010 2:01 pm

314 - WA - Why? Sample inputs?

Post by lucasbueno » Sun Oct 09, 2011 5:21 pm

I don't understand why my code is giving wrong answer, in these input (wich i get on another topic):

Code: Select all

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 south
2 3
0 0 0
0 0 0
1 1 1 2 west
5 5
0 0 0 0 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
0 0 0 0 0
1 1 4 4 east
2 3
0 0 0
0 0 1
1 1 1 2 east
0 0
The result was

Code: Select all

12
3
-1
-1
Is this correct?

Is there any special case? Someone have some test cases?

Thanks!

ConqerHeaven
New poster
Posts: 1
Joined: Fri Dec 07, 2012 4:46 pm

Re: 314 - Robot

Post by ConqerHeaven » Fri Dec 07, 2012 5:09 pm

Hi!For this problem ,my code is always WA,I had tried a lot of test cases and all right,I really don't know why it is WA,can any one tell me or give me a special test case? :( Thanks very much!
MY CODE:

Code: Select all

#include<iostream>
#include<queue>
#include<map>
using namespace std;
const int maxn = 60;
struct point{
	int x;
	int y;
	int step;
	int now_d;
}P[maxn*maxn];
struct direc{
	int x;
	int y;
}D[4];
map<string , int> ini_direc;
class Robot{
private:
	int r;
	int c;
	int chat[maxn][maxn];
	int chat1[maxn][maxn][4];
	point start;
	point end;
	int cnt;
public:
	void initial();
	void readcase(int a , int b);
	void computing();
	void change();
};
void Robot::initial(){
	r = 0;
	c = 0;
	for(int i = 0;i < maxn;i++){
		for(int j = 0;j < maxn;j++){
			chat[i][j] = 0;
			chat1[i][j][0] = 1;
			chat1[i][j][1] = 1;
			chat1[i][j][2] = 1;
			chat1[i][j][3] = 1;
		}
	}
	start.x = 0;
	start.y = 0;
	end.x = 0;
	end.y = 0;
	ini_direc["east"] = 0;
	ini_direc["south"] = 1;
	ini_direc["west"] = 2;
	ini_direc["north"] = 3;
	start.step = 0;
	end.step = 0;
	cnt = 0;
}
void Robot::readcase(int a, int b){
	r = a;
	c = b;
	for(int i = 0;i < a;i++){
		for(int j = 0;j < b;j++){
			cin >> chat[i][j];
		}
	}
	change();
	cin >> start.x >> start.y >> end.x >> end.y;
	string str;
	cin >> str;
	start.now_d = ini_direc[str];
	chat1[start.x][start.y][start.now_d] = 1;
	/*for(int i = 1;i < r;i++){
		for(int j = 1;j < c;j++){
			cout << chat1[i][j][0]<<" "<<chat1[i][j][1]<<"  ";
		}
		cout << endl;
		for(int j = 1;j < c;j++){
			cout << chat1[i][j][1]<<" "<<chat1[i][j][2]<<"  ";
		}
		cout << endl;
		cout << endl;
	}*///check the status matrix
}
void Robot::change(){
	for(int i = 1;i < r;i++){
		for(int j = 1;j < c;j++){
			if(chat[i][j] == 0&&chat[i][j-1] == 0&&chat[i-1][j] == 0&&chat[i-1][j-1] == 0){
				chat1[i][j][0] = 0;
				chat1[i][j][1] = 0;
				chat1[i][j][2] = 0;
				chat1[i][j][3] = 0;
			}
		}
	}
}
void Robot::computing(){
	if(chat1[end.x][end.y][0] == 1){
		cout << -1 << endl;
		return ;
	}
	for(int i = 0;i < 4;i++){
		if(i != start.now_d){
			chat1[start.x][start.y][i] = 0;
		}
	}
	queue<point> q;
	q.push(start);
	if(start.x == end.x && start.y == end.y){
		cout << '0' << endl;
		return;
	}
	while(! q.empty()){
		point P0 , P1;
		P0 = q.front();
		q.pop();
		int find = 0;
		for(int i = 0;i < 4;i++){
			P1.x = P0.x;
			P1.y = P0.y;
			P1.step = P0.step+1;
			if(P0.now_d != i && i - P0.now_d != 2 && i - P0.now_d != -2&& chat1[P1.x][P1.y][i] == 0){
				P1.now_d = i;
				q.push(P1);
				chat1[P1.x][P1.y][P1.now_d] = 1;
		    }
		}
		for(int i = 1;i <= 3;i++){
			P1.x = P0.x+D[P0.now_d].x*i;
			P1.y = P0.y+D[P0.now_d].y*i;
			P1.now_d = P0.now_d;
			if(P1.x >= 0 && P1.x <= r && P1.y >= 0 && P1.y <= c){
			if(chat1[P1.x][P1.y][P1.now_d] == 1){
				break;
			}
			P1.step = P0.step+1;
			q.push(P1);
			chat1[P1.x][P1.y][P1.now_d] = 1;
			if(P1.x == end.x && P1.y == end.y){
				cnt = P1.step;
				find = 1;
				break;
			}
			}
		}
		if(find){
			cout << cnt << endl;
			break;
		}
	}
	/*for(int i = 1;i < r;i++){
		for(int j = 1;j < c;j++){
			cout << chat1[i][j][0]<<" "<<chat1[i][j][1]<<"  ";
		}
		cout << endl;
		for(int j = 1;j < c;j++){
			cout << chat1[i][j][1]<<" "<<chat1[i][j][2]<<"  ";
		}
		cout << endl;
		cout << endl;
	}*///check the status matrix
	if(q.empty()){
		cout << -1 << endl;
	}
}
int main(){
	D[0].x = 0;
	D[0].y = 1;
	D[2].x = 0;
	D[2].y = -1;
	D[1].x = 1;
	D[1].y = 0;
	D[3].x = -1;
	D[3].y = 0;
	Robot R;
	int a , b;
	while(cin >> a >> b && (a||b)){
		R.initial();
		R.readcase(a , b);
		R.computing();
	}
	return 0;
}

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

Re: 314 - Robot

Post by brianfry713 » Sat Dec 08, 2012 1:32 am

For this input:

Code: Select all

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 7 2 south
0 0
My AC code prints 0
Check input and AC output for thousands of problems on uDebug!

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

Re: 314, Robot, Help!

Post by Munchor » Fri Mar 29, 2013 2:27 am

My program (used BFS) doesn't even solve example IO, and I'd like some help with it, I've debugged as much as I possibly can:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

#define MAX_SIDE 51

struct node
{
  int x;
  int y;
  int time;
  int direction;
};

int m, n, b[2], e[2], grid[MAX_SIDE][MAX_SIDE], min_time, visited[MAX_SIDE][MAX_SIDE][4];
queue<node> q;
char direction[6];
char directions[4][6] = {"north", "west", "south", "east"};
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
int i, u;

inline int min(int a, int b)
{
  return a < b ? a : b;
}

int read_input()
{
  scanf("%d %d", &m, &n);

  if (m == 0 && n == 0)
  {
    return 0;
  }

  //memset(grid, 0, sizeof grid);

  for (i = 0; i < m; i++)
  {
    for (u = 0; u < n; u++)
    {
      scanf("%d", &grid[i][u]);
      //printf("%d", grid[i][u]);
    }

    //printf("\n");
  }

  scanf("%d %d %d %d %s", &b[1], &b[0], &e[1], &e[0], direction);

  return 1;
}

int turn(int direction, int to_the_right)
{
  if (to_the_right)
  {
    if (direction == 0)
      return 3;
    else if (direction == 1)
      return 0;
    else if (direction == 2)
      return 1;
    else if (direction == 3)
      return 2;
  }
  else
  {
    if (direction == 0)
      return 1;
    else if (direction == 1)
      return 2;
    else if (direction == 2)
      return 3;
    else if (direction == 3)
      return 0;
  }
}

void bfs()
{
  memset(visited, -1, sizeof visited);

  while (!q.empty())
  {
    node current = q.front();
    q.pop();

    int x = current.x;
    int y = current.y;
    int time = current.time;
    int direction = current.direction;

    if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == 1)
    {
      continue;
    }

    if (visited[y][x][direction] != -1)
    {
      if (time >= visited[y][x][direction])
      {
        continue;
      }
    }

    printf("x = %d, y = %d, time = %d, direction = %d\n", x, y, time, direction);
    visited[y][x][direction] = time;

    if (x == e[0] && y == e[1])
    {
      printf("time: %d\n", time);

      if (min_time == -1)
        min_time = time;
      else
        min_time = min(min_time, time);
    }

    node new_node;
    new_node.time = time + 1;
    new_node.x = x;
    new_node.y = y;
    new_node.direction = turn(direction, 0);
    q.push(new_node);
    new_node.direction = turn(direction, 1);
    q.push(new_node);
    new_node.direction = direction;

    int s;
    bool wall_ahead;
    for (s = 1; s < 4; s++)
    {
      wall_ahead = false;

      for (u = 1; u <= s; u++)
      {
        if (grid[y + dy[direction]][x + dx[direction]] == 1 ||
            grid[y + dy[direction]][x + 1 + dx[direction]] == 1 ||
            grid[y + 1 + dy[direction]][x + dx[direction]] == 1 ||
            grid[y + 1 + dy[direction]][x + 1 + dx[direction]] == 1)
        {
          wall_ahead = true;
          break;
        }
      }

      if (wall_ahead)
      {
        break;
      }

      new_node.x = x + (dx[direction] * s);
      new_node.y = y + (dy[direction] * s);

      q.push(new_node);

      //printf("new_node.x = %d, new_node.y = %d, new_node.time = %d, k = %d, s = %d\n",
      //       new_node.x, new_node.y, new_node.time, k, s);
    }
  }
}

int main()
{
  while (read_input())
  {
    node start;
    start.x = b[0];
    start.y = b[1];
    start.time = 0;
    min_time = -1;

    /* Get initial direction */
    int k;
    for (k = 0; k < 4; k++)
    {
      if (strcmp(direction, directions[k]) == 0)
      {
        start.direction = k;
      }
    }

    q.push(start);
    bfs();

    printf("%d\n", min_time); // min time
  }

  return 0;
}

Code: Select all

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 south
0 0
For the example case it returns "6" instead of "12" and my BFS is very simple, I just push states and work them out, I have also made sure that I don't collide with grids and that the whole diameter of the robot is able to get to the goal.

I have also made sure I read coordinates (row, column) the right way.

Any ideas?

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

Re: 314, Robot, Help!

Post by brianfry713 » Fri Mar 29, 2013 10:40 pm

Your code prints for the sample output:
x = 3, y = 7, time = 2, direction = 3
You shouldn't be able to move onto 3,7 as there is an obstacle in the upper right. See the picture in the problem statement.
Check input and AC output for thousands of problems on uDebug!

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

Re: 314, Robot, Help!

Post by Munchor » Fri Mar 29, 2013 11:19 pm

Code: Select all

#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

#define MAX_SIDE 51

struct node
{
  int x;
  int y;
  int time;
  int direction;
};

int m, n, b[2], e[2], grid[MAX_SIDE][MAX_SIDE], min_time, visited[MAX_SIDE][MAX_SIDE][4];
queue<node> q;
char direction[6];
char directions[4][6] = {"north", "west", "south", "east"};
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};
int i, u;

inline int min(int a, int b)
{
  return a < b ? a : b;
}

int read_input()
{
  scanf("%d %d", &m, &n);

  if (m == 0 && n == 0)
  {
    return 0;
  }

  //memset(grid, 0, sizeof grid);

  for (i = 0; i < m; i++)
  {
    for (u = 0; u < n; u++)
    {
      scanf("%d", &grid[i][u]);
      //printf("%d", grid[i][u]);
    }

    //printf("\n");
  }

  scanf("%d %d %d %d %s", &b[1], &b[0], &e[1], &e[0], direction);

  return 1;
}

int turn(int direction, int to_the_right)
{
  if (to_the_right)
  {
    if (direction == 0)
      return 3;
    else if (direction == 1)
      return 0;
    else if (direction == 2)
      return 1;
    else if (direction == 3)
      return 2;
  }
  else
  {
    if (direction == 0)
      return 1;
    else if (direction == 1)
      return 2;
    else if (direction == 2)
      return 3;
    else if (direction == 3)
      return 0;
  }
}

void bfs()
{
  memset(visited, -1, sizeof visited);

  while (!q.empty())
  {
    node current = q.front();
    q.pop();

    int x = current.x;
    int y = current.y;
    int time = current.time;
    int direction = current.direction;

    if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == 1 || grid[y][x - 1] == 1 || grid[y - 1][x] == 1 || grid[y - 1][x - 1] == 1)
    {
      continue;
    }

    if (visited[y][x][direction] != -1)
    {
      if (time >= visited[y][x][direction])
      {
        continue;
      }
    }

    //printf("x = %d, y = %d, time = %d, direction = %d\n", x, y, time, direction);
    visited[y][x][direction] = time;

    if (x == e[0] && y == e[1])
    {
      //printf("time: %d\n", time);

      if (min_time == -1)
        min_time = time;
      else
        min_time = min(min_time, time);
    }

    node new_node;
    new_node.time = time + 1;
    new_node.x = x;
    new_node.y = y;
    new_node.direction = turn(direction, 0);
    q.push(new_node);
    new_node.direction = turn(direction, 1);
    q.push(new_node);
    new_node.direction = direction;

    int s;
    bool wall_ahead;
    for (s = 1; s < 4; s++)
    {
      wall_ahead = false;

      for (u = 1; u <= s; u++)
      {
        if (grid[y + dy[direction]][x + dx[direction]] == 1 ||
            grid[y + dy[direction]][x + 1 + dx[direction]] == 1 ||
            grid[y + 1 + dy[direction]][x + dx[direction]] == 1 ||
            grid[y + 1 + dy[direction]][x + 1 + dx[direction]] == 1)
        {
          wall_ahead = true;
          break;
        }
      }

      if (wall_ahead)
      {
        break;
      }

      new_node.x = x + (dx[direction] * s);
      new_node.y = y + (dy[direction] * s);

      q.push(new_node);

      //printf("new_node.x = %d, new_node.y = %d, new_node.time = %d, k = %d, s = %d\n",
      //       new_node.x, new_node.y, new_node.time, k, s);
    }
  }
}

int main()
{
  while (read_input())
  {
    node start;
    start.x = b[0];
    start.y = b[1];
    start.time = 0;
    min_time = -1;

    /* Get initial direction */
    int k;
    for (k = 0; k < 4; k++)
    {
      if (strcmp(direction, directions[k]) == 0)
      {
        start.direction = k;
      }
    }

    q.push(start);
    bfs();

    printf("%d\n", min_time); // min time
  }

  return 0;
}
Thanks Brianfry! I fixed it and it now works for the following input:

Code: Select all

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 south
9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 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 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 south
0 0
0 0
Thanks brianfry, It now solves the first example input, but the second one I made doesn't work, I used the toolkit and I got "12 7" but my program outputs "12 8."

I read some of the earlier comments and it seems like the robot can't walk on the grids but I think my program already works that way so I can't see what could be wrong.

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

Re: 314, Robot, Help!

Post by brianfry713 » Tue Apr 02, 2013 12:47 am

PM sent
Check input and AC output for thousands of problems on uDebug!

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

Re: 314, Robot, Help!

Post by Munchor » Fri Apr 05, 2013 2:58 am

I'm just leaving the tip here - be careful with collision, it's tricky!

????????
New poster
Posts: 5
Joined: Mon Nov 11, 2013 7:00 pm

Re: 314 - Robot

Post by ???????? » Sun Dec 22, 2013 9:49 am

why wa??i've used simple bfs..someone pls help..

Code: Select all

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<map>
#define loop(i,a,b) for (i=a;i<=b;i++)
#define set_zero(a) memset(a,0,sizeof(a))
#define pb push_back
#define valid(m,n) m>=1 && m<row && n>=1 && n<col

int row,col;
int board[55][55];
using namespace std;


bool no_obstacle(int a, int b)
{
    if (board[a][b] || board[a-1][b] || board[a][b-1] || board[a-1][b-1]) return false;
    return true;
}
struct node
{
    int x,y,movee,dir;
    node(int a,int b,int c,int d)
    {
        x=a; y=b; dir=c;movee=d;
    }
    bool operator < (const node&p) const {return movee>p.movee;}
};


int main()
{
    int row,col,i,j,k,m,n;

    int nx[]={0,0,1,-1};
    int ny[]={1,-1,0,0};
    char direction_1[]="1320";

  

    while(scanf("%d%d",&row,&col)==2 && (row||col))
    {

        set_zero(board);
        string dd;
        int src_x,src_y,dst_x,dst_y;

        int direction;

        loop(i,0,row-1)
            loop(j,0,col-1)
            {
                scanf("%d",&m);
                if (m) board[i][j]=1;
            }
        scanf("%d%d%d%d",&src_x,&src_y,&dst_x,&dst_y);

        cin>>dd;

        if (src_x==dst_x && src_y==dst_y) {printf("0\n");continue;}

        if (board[src_x][src_y] || board[dst_x][dst_y]) {printf("-1\n");continue;}

        if (dd=="west") m=3;
        else if (dd=="east") m=1;
        else if (dd=="south") m=2;
        else m=0;

        priority_queue< node > q;
        int taken[row+1][col+1],dist[row+1][col+1];
        set_zero(taken);

        taken[src_x][src_y]=1;
        dist[src_x][src_y]=0;
        q.push(node(src_x,src_y,m,0));

        bool reach=false;

        while(!q.empty())
        {
            node top=q.top(); q.pop();

            int u=top.x;
            int v=top.y;

            if (u==dst_x && v==dst_y) {reach=true;break;}

            direction=top.dir;

            loop(i,0,3)
            {
                int n=direction_1[i]-'0';
                int dir_diff=fabs(direction-n);

                if (dir_diff>2) dir_diff=1;

                loop(j,1,3)
                {
                    int x=u+(nx[i])*j; int y=v+(ny[i])*j;

                    if (valid(x,y)&& no_obstacle(x,y))
                    {
                        if (!taken[x][y])
                        {
                            taken[x][y]=1;

                            dist[x][y]=dist[u][v]+1+dir_diff;

                            q.push(node(x,y,n,dist[x][y]));
                        }
                    }
                    else break;
                }
            }
        }

        if (reach) printf("%d\n",dist[dst_x][dst_y]);
        else printf("-1\n");
    }
    return 0;
}


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

Re: 314 - Robot

Post by brianfry713 » Thu Jan 16, 2014 3:49 am

Use abs instead of fabs
Check input and AC output for thousands of problems on uDebug!

mehrab2603
New poster
Posts: 9
Joined: Sun Mar 30, 2014 6:56 pm

Re: 314, Robot, Help!

Post by mehrab2603 » Mon Apr 07, 2014 3:18 pm

Getting WA. Please help!

Code: Select all

#include <bits/stdc++.h>
#define MAX 55

using namespace std;


void trans(int, int);
int m, n, mat[MAX][MAX], mat2[MAX][MAX];
struct square{int x, y, dir; square() {} square(int a, int b) {x = a; y = b;} square(int a, int b, int c) {x = a; y = b; dir = c;}};
map<string, int> mymap;
int bfs(square, square);
int dirx[] = {1, 0, -1, 0};
int diry[] = {0, -1, 0, 1};
int face[] = {0, 1, 2, 3};
bool vis2[MAX][MAX];

int main()
{
    mymap["south"] = 0;
    mymap["west"] = 1;
    mymap["north"] = 2;
    mymap["east"] = 3;
    while(scanf("%d %d", &m, &n) && (m || n))
    {
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                scanf("%d", &mat2[i][j]);

/*
        cout << "original" << endl;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                cout << mat2[i][j];
            }
            cout << endl;
        }
*/
        memset(vis2, false, sizeof(vis2));
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(!vis2[i][j]) trans(i, j);

/*
        cout << "treansformed" << endl;
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                cout << mat[i][j];
            }
            cout << endl;
        }

*/
        int b1, b2, e1, e2;
        string dir;
        cin >> b1 >> b2 >> e1 >> e2 >> dir;
        square start(b1, b2, mymap[dir]), dest(e1, e2);
        int result = bfs(start, dest);
        if(result != -1) printf("%d\n", result);
        else printf("-1\n");
    }
    return 0;
}

int bfs(square start, square dest)
{
    int dist[MAX][MAX][4];
    bool vis[MAX][MAX][4];
    memset(vis, false, sizeof(vis));
    queue<square> q;
    dist[start.x][start.y][start.dir] = 0;
    vis[start.x][start.y][start.dir] = true;
    q.push(start);
    while(!q.empty())
    {
        square top = q.front();
        q.pop();
        int ux = top.x, uy = top.y, udir = top.dir;
        if(ux == dest.x && uy == dest.y)
                return dist[ux][uy][udir];
        for(int i = 0; i < 5; i++)
        {
            int vx, vy, vdir;
            if(i == 0)
            {
                vx = ux + dirx[udir];
                vy = uy + diry[udir];
                vdir = udir;
            }
            else if(i == 1)
            {
                vx = ux;
                vy = uy;
                vdir = (udir + 1 + 4) % 4;
            }
            else if(i == 2)
            {
                vx = ux;
                vy = uy;
                vdir = (udir - 1 + 4) % 4;
            }
            else if(i == 3)
            {
                int tempx = ux + dirx[udir];
                int tempy = uy + diry[udir];
                if(tempx > 0 && tempx < m && tempy > 0 && tempy < n && mat[tempx][tempy] != 1)
                {
                    vx = tempx + dirx[udir];
                    vy = tempy + diry[udir];
                    vdir = udir;
                }
                else continue;
            }
            else if(i == 4)
            {
                int tempx = ux + dirx[udir];
                int tempy = uy + diry[udir];
                if(tempx > 0 && tempx < m && tempy > 0 && tempy < n && mat[tempx][tempy] != 1)
                {
                    tempx = tempx + dirx[udir];
                    tempy = tempy + diry[udir];
                    if(tempx > 0 && tempx < m && tempy > 0 && tempy < n && mat[tempx][tempy] != 1)
                    {
                        vx = tempx + dirx[udir];
                        vy = tempy + diry[udir];
                        vdir = udir;
                    }
                    else continue;
                }
                else continue;
            }
            if(vx > 0 && vx < m && vy > 0 && vy < n && mat[vx][vy] != 1 && !vis[vx][vy][vdir])
            {
                vis[vx][vy][vdir] = true;
                dist[vx][vy][vdir] = dist[ux][uy][udir] + 1;
                q.push(square(vx, vy, vdir));
            }
        }
    }
    return -1;
}

void trans(int i, int j)
{
    vis2[i][j] = true;
    if(mat2[i][j])
    {
        mat[i][j] = 1;
        if(i + 1 <= m) {mat[i + 1][j] = 1; vis2[i + 1][j] = true;}
        if(j + 1 <= n) {mat[i][j + 1] = 1; vis2[i][j + 1] = true;}
        if(i + 1 <= m && j + 1 <= n) {mat[i + 1][j + 1] = 1; vis2[i + 1][j + 1] = true;}
    }
    else
        mat[i][j] = mat2[i][j];
}


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

Re: 314, Robot, Help!

Post by brianfry713 » Mon Apr 07, 2014 9:32 pm

Input:

Code: Select all

31 7
1 1 0 1 0 0 1
1 1 0 0 1 0 0
0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 1 0 0 0 1 0
0 1 1 1 0 1 0
0 1 0 0 0 1 1
0 1 1 1 1 0 1
1 1 1 0 0 0 0
0 1 0 1 0 1 0
0 0 0 0 1 0 0
0 1 1 0 0 0 1
1 0 0 0 1 0 0
1 0 1 0 1 1 1
1 1 1 1 1 0 0
1 0 0 1 0 0 1
0 0 0 0 1 1 0
0 1 1 0 1 0 0
0 1 1 1 0 0 0
0 0 0 1 1 1 0
1 1 1 1 1 1 1
0 0 0 1 1 1 1
0 1 1 0 0 0 1
1 0 0 1 0 0 0
0 1 0 1 0 1 0
0 0 0 0 1 0 1
0 1 0 1 0 1 1
0 1 1 1 0 1 0
1 1 0 1 1 0 0
1 1 0 1 0 0 0
1 0 1 1 1 0 0
23 5 22 4 east
0 0
AC output -1
Check input and AC output for thousands of problems on uDebug!

jaostr
New poster
Posts: 1
Joined: Thu Sep 04, 2014 4:15 pm

314 - Robot

Post by jaostr » Thu Sep 04, 2014 4:23 pm

Hi all,
Are there any corner cases in this problem?
I checked all the I/O provided in this thread and everything was OK. Still, I'm getting WA..... Can anyone help?

Just in case, here's my code:

Code: Select all

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ii, int> ii_i;

const int MAX = 50 + 5;
int a[MAX][MAX];
int M, N;

queue<ii_i> qu;
            // N  E  S   W
int dr[4] = { -1, 0, 1,  0};
int dc[4] = {  0, 1, 0, -1};

bool invPos(const ii& p) {
  int r = p.first, c = p.second;
  if (r <= 0 || r > M-1 || c <= 0 || c > N-1) return true; // border
  if (a[r][c] == -2 || a[r-1][c] == -2  || a[r-1][c-1] == -2 || a[r][c-1] == -2) return true; // wall
  return false;
}

void add(const ii_i& p, int turn) {
  ii_i cand = ii_i(p.first, p.second);
  int& r = cand.first.first;
  int& c = cand.first.second;
  int cost = a[p.first.first][p.first.second] + 1 + turn;
  for (int i = 1; i <= 3; i++) {
    r += dr[cand.second];
    c += dc[cand.second];
    
    if (invPos(ii(r, c))) break;
    if (a[r][c] >= 0 && cost >= a[r][c]) continue; // marked, and it was a cheaper way
    qu.push(cand);
    a[r][c] = cost;
  }
}

int bfs(const ii_i& b, const ii& e) {
  while (!qu.empty()) qu.pop(); // clear
  int r = b.first.first, c = b.first.second;
  qu.push(b);
  a[r][c] = 0;
  while (! qu.empty()) {
    ii_i u = qu.front(); qu.pop();
    // straight
    add(u, 0);
    // left
    ii_i l(u.first, (u.second + 1) % 4);
    add(l, 1);
    // right
    ii_i r(u.first, (u.second + 3) % 4);
    add(r, 1);
    // back
    ii_i b(u.first, (u.second + 2) % 4); 
    add(b, 2);
  }
  
  return a[e.first][e.second];
}

int c2dir(char c) {
  if (c == 'n') return 0;
  if (c == 'e') return 1;
  if (c == 's') return 2;
  if (c == 'w') return 3;
  return -10000;
}

int main()
{
  freopen("input.txt", "r", stdin);
  
  while (true) {
    scanf("%d %d ", &M, &N);
    if (M == 0 && N == 0) break;
    for (int i = 0; i < M; i++) 
      for (int j = 0; j < N; j++) {
        int x;
        scanf("%d ", &x);
        a[i][j] = (x == 0) ? -1 : -2;
      }
    ii b, e;
    scanf("%d %d %d %d ", &b.first, &b.second, &e.first, &e.second);
    char buf[6];
    scanf("%5s ", buf);
    
    if (invPos(b) || invPos(e)) { // check fot invalid positions
      printf("-1\n");
      continue;
    }

    printf("%d\n", bfs(ii_i(b, c2dir(buf[0])), e));

    //for (int i = 0; i < M; i++) {
    //  for (int j = 0; j < N; j++) {
    //    printf("%4d", a[i][j]);
    //  }
    //  printf("\n");
    //}
  }
}

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

Re: 314 - Robot

Post by brianfry713 » Thu Sep 04, 2014 7:26 pm

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 3 (300-399)”