314 - Robot

[zobayer]

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.

[lucasbueno]

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]

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]

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

[Munchor]

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]

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.

[Munchor]

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]

PM sent

[Munchor]

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

[????????]

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]

Use abs instead of fabs

[mehrab2603]

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]

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

[jaostr]

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]

Don't read from a file.