USACO 2.4.2 – Overfencing

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

struct State {
	int i, j, d;
};
int main() {
	int W, H, d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}, v[400][400] = {{0}};
	char g[400][400];
	freopen("maze1.in", "r", stdin), freopen("maze1.out", "w", stdout);
	scanf("%d %d\n", &W, &H);
	W = 2 * W + 1, H = 2 * H + 1;
	queue<State> q;
	State s;
	for (int i = 1; i <= H; i++, getchar())
		for (int j = 1; j <= W; j++) {
			g[i][j] = getchar();
			if (g[i][j] == ' ') {
				int t = 0;
				if (i == 1 && ++t)			s = State{2, j, 1};
				else if (i == H && ++t)		s = State{H-1, j, 1};
				else if (j == 1 && ++t)		s = State{i, 2, 1};
				else if (j == W && ++t)		s = State{i, W-1, 1};
				if (t && (g[i][j] = 'X') && (v[s.i][s.j] = 1))
					q.push(s);
			}
		}
	
	while (q.size()) {
		s = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			State fence{s.i + d[i][0],s.j + d[i][1],0 };
			State cell{fence.i+d[i][0], fence.j+ d[i][1], s.d+1};
			if (g[fence.i][fence.j] == ' ' && !v[cell.i][cell.j]) {
				g[fence.i][fence.j] = 'X', v[cell.i][cell.j] = 1;
				q.push(cell);
			}
		}
	}
	printf("%d\n", s.d);
	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: