题目传送
1.这仅仅是一道加了传送门的bfs
2.仅仅加了一个传送门,就卡了我一下午
3.门存在不成对的情况。。。。。。。。。
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 305;
const int inf = 0x3f3f3f3f;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };
struct node {
int x, y;
node(int x = 0, int y = 0) :x(x), y(y) {}
}cs[30][2];
int n, m, qx, qy, zx, zy, fx, fy;
int map[maxn][maxn];
int step[maxn][maxn];
queue<node> q;
void ff(int x, int y)
{
if (cs[map[x][y] - 'A'][0].x != x || cs[map[x][y] - 'A'][0].y != y) {
fx = cs[map[x][y] - 'A'][0].x;
fy = cs[map[x][y] - 'A'][0].y;
}
else {
fx = cs[map[x][y] - 'A'][1].x;
fy = cs[map[x][y] - 'A'][1].y;
}
}
bool cheak(int x, int y)
{
return cs[map[x][y] - 'A'][1].x != 0;
}
void bfs()
{
memset(step, inf, sizeof(step));
step[qx][qy] = 0;
q.push(node(qx, qy));
while (q.size()) {
int x = q.front().x;
int y = q.front().y;
q.pop();
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (!map[xx][yy]) continue;
if (map[xx][yy] >= 'A' && map[xx][yy] <= 'Z' && cheak(xx, yy)) {
ff(xx, yy);
if (step[fx][fy] > step[x][y] + 1) {
step[fx][fy] = step[x][y] + 1;
q.push(node(fx, fy));
}
}
else if (step[xx][yy] > step[x][y] + 1) {
step[xx][yy] = step[x][y] + 1;
q.push(node(xx, yy));
}
}
}
}
int main(void)
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >> ch;
if (ch == '.') map[i][j] = 1;
else if (ch == '#') map[i][j] = 0;
else if (ch == '@') {
qx = i;
qy = j;
map[i][j] = 1;
}
else if (ch == '=') {
zx = i;
zy = j;
map[i][j] = 1;
}
else if (ch >= 'A' && ch <= 'Z') {
if (cs[ch - 'A'][0].x == 0) {
cs[ch - 'A'][0].x = i;
cs[ch - 'A'][0].y = j;
}
else {
cs[ch - 'A'][1].x = i;
cs[ch - 'A'][1].y = j;
}
map[i][j] = ch;
}
}
}
bfs();
cout << step[zx][zy] << endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)