Result: Accepted
Time: 7ms
Memory: 1788kB
#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;
}