Start: May, 31, 2017 13:30:00
2017ACM通识课期末考试
End: May, 31, 2017 17:30:00
Time elapsed:
Time remaining:

Problem_ID: J
Result: Accepted
Time: 7ms
Memory: 1788kB
Author: Darkmota
In contest: 1090

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <cstdlib>
using namespace std;

struct node{
	int x, y, t;
	node(int xx, int yy, int tt) {
		x = xx;
		y = yy;
		t = tt;
	}
};
queue<node> q;
int able[101][101], u[101][101];
char c;

int main() {
	int x, y, mx, my, placeleft, i, j, T = 0, xx, yy, tt;
	while (cin >> y >> x >> my >> mx) {
		placeleft = 0;
		memset(able, 0, sizeof(able));
		memset(u, 0, sizeof(u));
		for (i = 1; i <= x; i++) {
			for (j = 1; j <= y; j++) {
				cin >> c;
				if (c == '.') {
					placeleft++;
					able[i][j] = 1;
				}
			}
		}
		q.push(node(mx, my, 0));
		u[mx][my] = 1;
		placeleft--;
		while (++T, !q.empty()) {
			xx = q.front().x;
			yy = q.front().y;
			tt = q.front().t;
			q.pop();
			if (xx != x && able[xx+1][yy] && !u[xx+1][yy]) {
				q.push(node(xx+1,yy,tt+1));
				u[xx+1][yy] = 1;
				placeleft--;
				if(placeleft == 0) {
					cout << tt+1 << endl;
					break;
				}
			}
			if (xx != 0 && able[xx-1][yy] && !u[xx-1][yy]) {
				q.push(node(xx-1,yy,tt+1));
				u[xx-1][yy] = 1;
				placeleft--;
				if(placeleft == 0) {
					cout << tt+1 << endl;
					break;
				}
			}
			if (yy != y && able[xx][yy+1] && !u[xx][yy+1]) {
				q.push(node(xx,yy+1,tt+1));
				u[xx][yy+1] = 1;
				placeleft--;
				if(placeleft == 0) {
					cout << tt+1 << endl;
					break;
				}
			}
			if (yy != 0 && able[xx][yy-1] && !u[xx][yy-1]) {
				q.push(node(xx,yy-1,tt+1));
				u[xx][yy-1] = 1;
				placeleft--;
				if(placeleft == 0) {
					cout << tt+1 << endl;
					break;
				}
			}
			
			if (xx != x && yy != y && able[xx+1][yy+1] && !u[xx+1][yy+1]) {
				q.push(node(xx+1,yy+1,tt+1));
				u[xx+1][yy+1] = 1;
				placeleft--;
				if(placeleft == 0) {
					cout << tt+1 << endl;
					break;
				}
			}
			if (xx != 0 && yy != 0 && able[xx-1][yy-1] && !u[xx-1][yy-1]) {
				q.push(node(xx-1,yy-1,tt+1));
				u[xx-1][yy-1] = 1;
				placeleft--;
				if(placeleft == 0) {
					cout << tt+1 << endl;
					break;
				}
			}
			if (xx != x && yy != 0 && able[xx+1][yy-1] && !u[xx+1][yy-1]) {
				q.push(node(xx+1,yy-1,tt+1));
				u[xx+1][yy-1] = 1;
				placeleft--;
				if(placeleft == 0) {
					cout << tt+1 << endl;
					break;
				}
			}
			
			if (xx != 0 && yy != y && able[xx-1][yy+1] && !u[xx-1][yy+1]) {
				q.push(node(xx-1,yy+1,tt+1));
				u[xx-1][yy+1] = 1;
				placeleft--;
				if(placeleft == 0) {
					cout << tt+1 << endl;
					break;
				}
			}
			/*
			for (i = 1; i <= x; i++)
			{
				for (j = 1; j <= y; j++)
				{
					if (u[i][j]) cout <<'M';
					else if (!able[i][j]) cout << '*';
					else cout << '.';
				}
				cout << endl;
			}
			cout << endl;
			*/
		}
	}
	return 0;
}