PKU 21 MingRen and Zuozhu

Problem: http://acmicpc.openjudge.cn/practice/021/


#include<iostream>
#include<queue>
using namespace std;
string a[205];
bool v[205][205][15];
int dx[5] = {-1, 0, 0, 1};
int dy[5] = {0, -1, 1, 0};
int n, m, t;

struct node {
	int x;
	int y;
	int num;
	int level;
	node(int xx, int yy, int numm, int levell) {
		x = xx;
		y = yy;
		num = numm;
		level = levell;
	}
};

bool inrange(int x, int y) {
	if (x >= 0 && x < m && y >= 0 && y < n) {
		return true;
	} 
	return false;
}

int main() {
	cin >> m >> n >> t;
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	int sx, sy;
	int ex, ey;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (a[i][j] == '@')	{
				sx = i;
				sy = j;
			} else if (a[i][j] == '+') {
				ex = i;
				ey = j;
			}
		}
	}
	queue<node> q;
	q.push(node(sx, sy, t, 0));
	v[sx][sy][t] = true;
	while(!q.empty()) {
		node k = q.front();
		q.pop();
		if (k.x == ex && k.y == ey) {
			cout << k.level;
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			int x = k.x + dx[i];
			int y = k.y + dy[i];
			if (inrange(x, y)) {
				if (a[x][y] == '#' && !v[x][y][k.num - 1]) {
					if (k.num > 0) {
						q.push(node(x, y, k.num - 1, k.level + 1));
						v[x][y][k.num - 1] = true;
					} else {
						continue;
					}
				} else if (a[x][y] != '#' && !v[x][y][k.num]){
					q.push(node(x, y, k.num, k.level + 1));
					v[x][y][k.num] = true;
				}
			}
		}
	}
	cout << "-1";
	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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s