垃圾题目写吐了
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define maxn 305
#define maxm 300
struct node {
int x = 0, y = 0;
long long step = 0;
node(int x1 = 0, int y1 = 0, int step1 = 0) {
x = x1, y = y1, step = step1;
}
};
struct door {
char c;
int x1 = 0, y1 = 0;
int x2 = 0, y2 = 0;
door(char c1, int x_1 = 0, int y_1 = 0, int x_2 = 0, int y_2 = 0) {
c = c1, x1 = x_1, y1 = y_1, x2 = x_2, y2 = y_2;
}
};
int n, m;
char ch[maxn][maxm];
queue<node> Q;
vector<door> V;
int start_x, start_y, end_x, end_y;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
bool vis[maxn][maxm];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++) {
cin >> ch[i][j];
if(ch[i][j] == '@')
start_x = i, start_y = j;
else if(ch[i][j] == '=')
end_x = i, end_y = j;
else if(ch[i][j] >= 'A' && ch[i][j] <= 'Z') {
int flag = 0;
for(int k = 0; k < V.size(); k ++)
if(V[k].c == ch[i][j]) {
V[k].x2 = i, V[k].y2 = j;
flag = 1;
break;
}
if(!flag) {
door tmp = door(ch[i][j], i, j);
V.push_back(tmp);
}
}
}
node tmp = node(start_x, start_y, 0);
Q.push(tmp);
while(!Q.empty()) {
tmp = Q.front();
int tx = tmp.x, ty = tmp.y;
for(int i = 0; i < 4; i ++) {
int x = tx + dx[i], y = ty + dy[i];
if(!vis[x][y]) {
vis[x][y] = true;
if(x == end_x && y == end_y) {
cout << tmp.step + 1;
return 0;
}
if(x < 1 || x > n || y < 1 || y > m || vis[x][y])
continue;
if(ch[x][y] == '.' && !vis[x][y]) {
node nd = node(x, y, tmp.step + 1);
Q.push(nd);
} else if(ch[x][y] >= 'A' && ch[x][y] <= 'Z') {
for(int i = 0; i < V.size(); i ++) {
if(V[i].x1 == x && V[i].y1 == y && !vis[V[i].x1][V[i].y1]) {
node n1 = node(V[i].x2, V[i].y2, tmp.step + 1);
Q.push(n1);
}
if(V[i].x2 == x && V[i].y2 == y && !vis[V[i].x2][V[i].y2]) {
node n2 = node(V[i].x1, V[i].y1, tmp.step + 1);
Q.push(n2);
}
}
} else if(ch[x][y] == '#')
continue;
}
}
}
cout << "NO ANSWER!";
return 0;
}