怎么就死循环了呢。。。。。。
查看原帖
怎么就死循环了呢。。。。。。
742157
ZYK_luogu楼主2023/4/9 20:06

垃圾题目写吐了

#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;
}

2023/4/9 20:06
加载中...