1202 - Finding Nemo

[brianfry713]

Use this thread to discuss this problem.

[NAbdulla]

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

Thanks in advance.