## 1202 - Finding Nemo

Moderator: Board moderators

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

### 1202 - Finding Nemo

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

NAbdulla
New poster
Posts: 31
Joined: Wed Jul 30, 2014 3:40 pm
Contact:

### Re: 1202 - Finding Nemo

Can anyone help me to find the error? I am getting WA...

my code:

Code: Select all

``````#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <climits>

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <ios>
#include <set>
#include <map>

using namespace std;

#define PI acos(-1.0)
#define EPS 1e-9
#define INF 1 << 28
#define sq(a) ((a) * (a))
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define ppb() pop_back()
#define mp(a, b) make_pair(a, b)
#define endl '\n'
#define MAX 100000
#define MOD 1000000007
#define dprint(expr) printf(#expr " = %lf\n", expr)

inline bool isEq(double a, double b){return (abs(a-b) < EPS);}
inline double NegZero(double x){if(isEq(x, -0.0))return +0.0;else return x;}

typedef long long ll;
typedef pair<int, int> pii;

#define isValid(a, min, max) ((a >= min && a <= max) ? 1 : 0)
int dx[]  =  {0, 1, 0, -1};
int dy[]  =  {1, 0, -1, 0};
int maxX, maxY, minX, minY;
char maze[205][205][4];//a cell in the maze and its four sides' information

int bfs(int a, int b)
{
queue<pii>Q;
Q.push(mp(a, b));
bool vis[205][205] = {0};
vis[a][b] = 1;
int level[205][205];
level[a][b] = 0;

//0 means up side of cell maze[a][b]
//1 means right side of cell maze[a][b]
//2 means down side of cell maze[a][b]
//3 means left side of cell maze[a][b]

if (a == minX && maze[a][b][3] == 'd'){
return level[a][b] + 1;
}
else if (a == maxX && maze[a][b][1] == 'd'){
return level[a][b] + 1;
}
else if (b == minY && maze[a][b][2] == 'd'){
return level[a][b] + 1;
}
else if (b == maxY && maze[a][b][0] == 'd'){
return level[a][b] + 1;
}

while(!Q.empty()){
pii u = Q.front();
Q.pop();
int x = u.first;
int y = u.second;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if((isValid(nx, minX, maxX) && isValid(ny, minY, maxY)) && !vis[nx][ny] && maze[x][y][i] == 'd'){//visiting cell is inside the maze and not visited and there is a door to go from maze[x][y] to maze[nx][ny]
vis[nx][ny] = 1;
level[nx][ny] = level[x][y] + 1;

//trying to find a way to go out of the maze
if(nx == minX && maze[nx][ny][3] == 'd'){
return level[nx][ny]+1;
}
else if(nx == maxX && maze[nx][ny][1] == 'd'){
return level[nx][ny]+1;
}
else if(ny == minY && maze[nx][ny][2] == 'd'){
return level[nx][ny]+1;
}
else if(ny == maxY && maze[nx][ny][0] == 'd'){
return level[nx][ny]+1;
}

//if can't go out then push this cell to the queue
Q.push(mp(nx, ny));
}
}
}
return -1;
}

int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//ios_base::sync_with_stdio(false); cin.tie(NULL);
int doors, walls;
while(cin >> walls >> doors){
if(doors == -1 && walls == -1)
break;

int x, y, d, t;
memset(maze, 0, sizeof(maze));
minX = minY = 600;
maxX = maxY = 0;
for(int i = 0; i < walls; i++){
cin >> x >> y >> d >> t;
minX = min(minX, x);
minY = min(minY, y);
if(d == 0){
maxX = max(maxX, x+t-1);
for(int nx = x; nx < x+t; nx++){
maze[nx][y][2] = maze[nx][y-1][0] = 'w';
}
}
else{
maxY = max(maxY, y+t-1);
for(int ny = y; ny < y+t; ny++){
maze[x][ny][3] = maze[x-1][ny][1] = 'w';
}
}
}
for(int i = 0; i < doors; i++){
cin >> x >> y >> d;
t = 1;
if(d == 0){
for(int nx = x; nx < x+t; nx++){
maze[nx][y][2] = maze[nx][y-1][0] = 'd';
}
}
else{
for(int ny = y; ny < y+t; ny++){
maze[x][ny][3] = maze[x-1][ny][1] = 'd';
}
}
}

/*cout << maxX << " " << maxY << endl << minX << " " << minY << endl << "x,y\tN E S W\n";
for(int i = minX; i <= maxX; i++){
for(int j = minY; j <= maxY; j++){
cout << i << "," << j << "\t";
for(int k = 0; k < 4; k++){
cout << maze[i][j][k] << ' ';
}
cout << endl;
}
}*/

double a, b;
cin >> a >> b;
int xx = a, yy = b;
if(xx < minX || xx > maxX || yy < minY || yy > maxY)
cout << 0 << endl;
else
cout << bfs(xx, yy) << endl;
}
return 0;
}
``````