现在菜到连 bfs 都不会了。。。。。
#include <iostream>
#include <queue>
using namespace std;
const int N = 300 + 7;
int n, m, flag;
int a[N][N], ans[N][N];
pair < int, int > go[N][N];
int q1, q2, x1, y1, x2, y2, z1, z2;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
queue < pair < int, int > > q;
pair < int, int > chh[N];
inline void bfs(int q1, int q2)
{
q.push(make_pair(q1, q2));
while(!q.empty())
{
if(flag) break;
int x = q.front().first, y = q.front().second;
q.pop();
a[x][y] = 1;
//cout << x << ' ' << y << endl;
for(int i=0; i<4; i++)
{
int tx = x + dx[i];
int ty = y + dy[i];
if(tx < 1 || ty < 1) continue;
if(tx > n || ty > m) continue;
if(a[tx][ty]) continue;
ans[tx][ty] = ans[x][y] + 1;
if(tx == z1 && ty == z2)
{
cout << ans[tx][ty] << endl;
flag = 1;
}
q.push(make_pair(tx, ty));
}
int nowx = go[x][y].first, nowy = go[x][y].second;
if(nowx && nowy)
ans[nowx][nowy] = ans[x][y], q.push(make_pair(nowx, nowy));
}
}
int main()
{
freopen("1.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
char ch;
cin >> ch;
if(ch == '=')
z1 = i, z2 = j;
if(ch == '#')
a[i][j] = 1;
if(ch == '.')
;
if(ch >= 'A' && ch <= 'Z')
{
if(chh[ch].first)
{
go[chh[ch].first][chh[ch].second] = make_pair(i, j);
go[i][j] = chh[ch];
}
else
chh[ch] = make_pair(i, j);
}
if(ch == '@')
q1 = i, q2 = j, a[i][j] = 1;
}
}
// cout << x1 << ' ' << y1 << endl;
// cout << x2 << ' ' << y2 << endl;
// cout << q1 << ' ' << q2 << endl;
// cout << z1 << ' ' << z2 << endl;
bfs(q1, q2);
}