UVA -10653 – Bombs! NO they are Mines!!

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int di[] = {-1, +0, +0, +1};
int dj[] = {+0, -1, +1, +0};
#define VALID(u, d, I, J) ((u).i+di[d]>=0 && (u).j+dj[d]>=0 && (u).i+di[d]<(I) && (u).j+dj[d]<(J))
struct P {
	int i, j;
	P(int I, int J) { i = I, j = J; }
};
int main() {
	int I, J, C, R, i, j, si, sj, ei, ej;
	while ((cin >> I >> J) && I && J && (cin >> R)) {
		int g[I][J];
		memset(g, 0, sizeof g);
		while (R-- && (cin >> i >> C))
			while (C-- && (cin >> j)) 	g[i][j] = 1;
		cin >> si >> sj >> ei >> ej;
		queue<P> que;
		g[si][sj] = 1;
		que.push(P(si, sj));
		while(que.size()){
			P u = que.front(); que.pop();
			for(int d=0; d<4; d++)
				if(VALID(u, d, I, J)  && !g[u.i+di[d]][u.j+dj[d]]){
					que.push(P(u.i + di[d], u.j+dj[d]));
					g[u.i+di[d]][u.j+dj[d]]= g[u.i][u.j] + 1;
				}
		}
		cout << (g[ei][ej]-1) << endl;
	}
	return 0;
}

Advertisements

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

%d bloggers like this: