PKU 20 Rescue Operation

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


#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int v[205][205] = {0};
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
int n, m;

struct node {
	int x;
	int y;
	int step;
	node(int tmpx, int tmpy, int tmpstep) {
		x = tmpx;
		y = tmpy;
		step = tmpstep;
	}
};

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

bool operator<(node a, node b) {
	return a.step > b.step;
}

int main() {
	int s;
	cin >> s;
	while (s--) {
		memset(v, 0, sizeof(v));
		priority_queue<node> q;
		int x, y, xx, yy;
		cin >> n >> m;	
		string a[205];
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}	
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (a[i][j] == 'r') {
					x = i;
					y = j;
				}
				if (a[i][j] == 'a') {
					xx = i;
					yy = j;
				}
			}
		}
		q.push(node(x, y, 0));
		v[x][y] = 1;
		while (!q.empty() && !(q.top().x == xx && q.top().y == yy)) {
			node tmp = q.top();
			// cout << tmp.x << ' ' << tmp.y << endl;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = tmp.x + dx[i];
				int ny = tmp.y + dy[i];
				if (inrange(nx, ny) && a[nx][ny] != '#'	&& !v[nx][ny]) {
					if (a[nx][ny] == 'x') {
						v[nx][ny] = 1; 
						q.push(node(nx, ny, tmp.step + 2));
					} else {
						v[nx][ny] = 1; 
						q.push(node(nx, ny, tmp.step + 1));
					}
				}
			}
		}
		if (q.empty()) {
			cout << "Impossible" << endl;
		} else {
			cout << q.top().step << 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 )

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