## 12069 - Robots inside the Labyrinth

Moderator: Board moderators

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

### 12069 - Robots inside the Labyrinth

Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!

shahidul_brur
New poster
Posts: 12
Joined: Sun Sep 20, 2015 12:33 pm

### Re: 12069 - Robots inside the Labyrinth

Getting WA.
Here is my code:

Code: Select all

``````/*==============================================*\
ID:          shahidul_brur

Name:     Md. Shahidul Islam
Study:      CSE, BRUR

mail: shahidul.cse.brur@gmail.com
FB  : fb.com/shahidul.brur
Blog: shahidul-brur.blogspot.com(in Bengali),
shahidul-brur-en.blogspot.com(in English)
\*===============================================*/
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;

const int maxn = 1005;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
struct Rec{
int x[2], y[2];
}rec[maxn];
struct Query{
int x[2], y[2];
}qu[maxn];
struct Data{
int val, index, typ, side;
bool operator < (const Data &other) const {
return val < other.val;
}
};
int mx, my;
int dis[maxn][maxn];
bool grid[maxn][maxn];
bool vis[maxn][maxn];
void bfs(int sx, int sy, int ex, int ey){
for(int i=0;i<=mx+1;i++)
for(int j=1;j<=my+1;j++)
vis[i][j]=grid[i][j]; // rectangle cell are kept visited
dis[sx][sy] = 0;
vis[sx][sy] = 1;
queue<ii> q;
q.push(make_pair(sx, sy));
int tmp = sx-1;
while(tmp>=0 && !vis[tmp][sy]) dis[tmp][sy]=0, vis[tmp][sy]=1, q.push(make_pair(tmp--, sy));
tmp=sx+1;
while(tmp<=mx+1 && !vis[tmp][sy]) dis[tmp][sy]=0, vis[tmp][sy]=1, q.push(make_pair(tmp++, sy));
tmp=sy-1;
while(tmp>=0 && !vis[sx][tmp]) dis[sx][tmp]=0, vis[sx][tmp]=1, q.push(make_pair(sx, tmp--));
tmp=sy+1;
while(tmp<=my+1 && !vis[sx][tmp]) dis[sx][tmp]=0, vis[sx][tmp]=1, q.push(make_pair(sx, tmp++));
while(!q.empty()){
sx=q.front().first;
sy=q.front().second;
q.pop();

int tmp = sx-1;
while(tmp>=0 && !vis[tmp][sy]){
dis[tmp][sy] = dis[sx][sy]+1;
vis[tmp][sy] = 1;
q.push(make_pair(tmp--, sy));
}
tmp=sx+1;
while(tmp<=mx+1 && !vis[tmp][sy]){
dis[tmp][sy] = dis[sx][sy]+1;
vis[tmp][sy] = 1;
q.push(make_pair(tmp++, sy));
}
tmp=sy-1;
while(tmp>=0 && !vis[sx][tmp]){
dis[sx][tmp] = dis[sx][sy]+1;
vis[sx][tmp] = 1;
q.push(make_pair(sx, tmp--));
}
tmp=sy+1;
while(tmp<=my+1 && !vis[sx][tmp]){
dis[sx][tmp] = dis[sx][sy]+1;
vis[sx][tmp] = 1;
q.push(make_pair(sx, tmp++));
}
}
if(vis[ex][ey]==0)
printf("Impossible.\n");
else printf("%d\n", dis[ex][ey]);
}
int main()
{
//ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int t;
scanf("%d", &t);
for(int cas=1;cas<=t;cas++){
int n;
scanf("%d", &n);
vector<Data> px, py;
for(int i=0;i<n;i++) {
int xl, xr, yd, yu;
scanf("%d %d %d %d", &xl, &yd, &xr, &yu);
Data data;
data.index=i,data.typ=0; // typ=0 means rectangle

data.side = 0, data.val = xl; px.push_back(data); // side=0 means left
data.side = 1, data.val = xr; px.push_back(data); // side=1 means right

data.side = 0, data.val = yd; py.push_back(data);
data.side = 1, data.val = yu; py.push_back(data);
}
int q;
scanf("%d", &q);
for(int i=0;i<q;i++){
int xl, xr, yd, yu;
scanf("%d %d %d %d", &xl, &yd, &xr, &yu);
Data data;
data.index=i,data.typ=1; // typ=1 means  query

data.side = 0, data.val = xl; px.push_back(data);
data.side = 1, data.val = xr; px.push_back(data);

data.side = 0, data.val = yd; py.push_back(data);
data.side = 1, data.val = yu; py.push_back(data);
}
sort(px.begin(), px.end());
sort(py.begin(), py.end());
int s = px.size();
mx=1,my=1;
for(int i=0;i<s;i++) {
if(i>0 && px[i].val==px[i-1].val+1) ++mx;
if(i>0 && px[i].val>px[i-1].val+1) mx+=2;
if(px[i].typ==0)
rec[px[i].index].x[px[i].side] = mx;
else qu[px[i].index].x[px[i].side] = mx;

if(i>0 && py[i].val==py[i-1].val+1) ++my;
if(i>0 && py[i].val>py[i-1].val+1) my+=2;
if(py[i].typ==0)
rec[py[i].index].y[py[i].side] = my;
else qu[py[i].index].y[py[i].side] = my;
}
for(int i=0;i<=mx+1;i++)
for(int j=0;j<=my+1;j++)
grid[i][j]=0;
for(int i=0;i<n;i++){
//            cout << rec[i].x[0] << " ";
//            cout << rec[i].y[0] << ", ";
//            cout << rec[i].x[1] << " ";
//            cout << rec[i].y[1] << "\n";
for(int r=rec[i].x[0];r<=rec[i].x[1];r++)
for(int c = rec[i].y[0];c<=rec[i].y[1];c++)
grid[r][c] = 1;
}
//        for(int i=0;i<=mx+1;i++){
//            for(int j=0;j<=my+1;j++)
//                cout << grid[i][j];
//            cout << "\n";
//        }
printf("Labyrinth #%d\n", cas);
for(int i=0;i<q;i++){
//            cout << qu[i].x[0] << " ";
//            cout << qu[i].y[0] << ", ";
//            cout << qu[i].x[1] << " ";
//            cout << qu[i].y[1] << " : ";
bfs(qu[i].x[0], qu[i].y[0], qu[i].x[1], qu[i].y[1]);
}
}
return 0;
}
``````
Can anyone give me any critical test case?