广搜写炸了,帮帮蒟蒻吧。
# include <bits/stdc++.h>
using namespace std;
char a[1000][1000];
struct Node
{
int x, y;
};
queue <Node> q;
int ans = 99999999;
int dir[5][3] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool vis[1000][1000];
int n, m;
void bfs(int dx, int dy, int csx, int csy, int cs1x, int cs1y)
{
int sum = 0;
Node start;
start.x = dx;
start.y = dy;
q.push(start);
while (!q.empty())
{
start = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = start.x + dir[i][0];
int ny = start.y + dir[i][1];
Node tmp;
tmp.x = nx;
tmp.y = ny;
if (a[nx][ny] != '#' && nx <= m && nx >= 1 && ny <= n && ny >= 1)
{
vis[nx][ny] = true;
if (a[nx][ny] == '.' && !vis[nx][ny])
{
q.push(tmp);
sum++;
}
if (a[nx][ny] == 'W')
{
if (nx == csx && ny == csy)
{
sum++;
nx = cs1x;
ny = cs1y;
tmp.x = nx;
tmp.y = ny;
q.push(tmp);
}
if (nx == cs1x && ny == cs1y)
{
sum++;
nx = csx;
ny = csy;
tmp.x = nx;
tmp.y = ny;
q.push(tmp);
}
}
if (a[nx][ny] == '=')
{
ans = min(ans, sum);
sum = 0;
}
}
}
}
}
int main()
{
cin >> m >> n;
int dx, dy;
int csx, csy;
int cs1x, cs1y;
int k = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
if (a[i][j] == '@')
{
dx = i;
dy = j;
}
if (a[i][j] == 'W' && k == 0)
{
csx = i;
csy = j;
k = 1;
}
if (a[i][j] == 'W' && k == 1)
{
cs1x = i;
cs1y = j;
}
}
}
bfs(dx, dy, csx, csy, cs1x, cs1y);
cout << ans << endl;
// system("pause");
return 0;
}