Posted in ACM-ICPC, BFS, Kuangbin

POJ 3984/ kuangbin 1K/ maze problem

Problem: http://poj.org/problem?id=3984
Solution: BFS.

#include
#include
#include
#include
using namespace std;

int a[6][6] = {0};
int vis[6][6] = {0};
int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, -1, 0, 1};
int prevx[6][6] = {0};
int prevy[6][6] = {0};

struct T {
	int x;
	int y;
	void init(int a, int b) {
		x = a;
		y = b;
	}
};

queue q;
stack ans;

void print(int x, int y) {
	if (x != 0 || y != 0) {
		T temp;
		temp.init(x, y);
		ans.push(temp);
		print(prevx[x][y], prevy[x][y]);
	}
}

void bfs(T temp) {
	int m = temp.x;
	int n = temp.y;
	if (m == 5 && n == 5) {
		print(m, n);
	} else {
		q.pop();
		for (int i = 1; i = 1 && m + dx[i] = 1 && n + dy[i] <= 5 && 
						a[m + dx[i]][n + dy[i]] == 0 && vis[m + dx[i]][n + dy[i]] == 0) {
				vis[m + dx[i]][n + dy[i]] = 1;
				T temp;
				temp.init(m + dx[i], n + dy[i]);
				prevx[m + dx[i]][n + dy[i]]	= m;
				prevy[m + dx[i]][n + dy[i]] = n;
				q.push(temp);
			}
		}
		bfs(q.front());
	}
}

int main () {
	for (int i = 1; i  a[i][j];
		}
	}
	T temp;
	temp.init(1, 1);
	prevx[temp.x][temp.y] = 0;
	prevy[temp.x][temp.y] = 0;
	vis[temp.x][temp.y] = 1;
	q.push(temp);
	bfs(temp);
	while(!ans.empty()) {
		cout << '(' << ans.top().x - 1 << ", " << ans.top().y - 1 << ')';
		ans.pop();
		if (!ans.empty()) {
			cout << endl;
		}
	}
	return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s