## 314 - Robot

Moderator: Board moderators

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### 314 - Robot

Code: Select all

``````Accepted
``````
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?

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

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;
}
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.computing();
}
return 0;
}
``````

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

### Re: 314 - Robot

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!

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;
}

{
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;
for (s = 1; s < 4; s++)
{

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)
{
break;
}
}

{
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()
{
{
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!

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!

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;
}

{
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;
for (s = 1; s < 4; s++)
{

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)
{
break;
}
}

{
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()
{
{
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!

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!

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

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

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!

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!

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

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
// left
ii_i l(u.first, (u.second + 1) % 4);
// right
ii_i r(u.first, (u.second + 3) % 4);
// back
ii_i b(u.first, (u.second + 2) % 4);
}

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