求助
查看原帖
求助
531776
LYM20114楼主2022/8/8 11:36

19分 WA了好多

#include <iostream>
#include <queue>
#include <map>
using namespace std;
int n,m,sx,sy,ex,ey;
int res[355][355];
char c[355][355];
bool vis[355][355];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool check(int x,int y){
	if(x < 1 || x > n || y < 1 || y > m) return false;
	else return true;
}
void bfs(int x,int y){
	queue <int> qx;
	queue <int> qy;
	qx.push(x);qy.push(y);
	vis[x][y] = 1;
	while(!qx.empty() && !qy.empty()){
		int nx = qx.front();
		int ny = qy.front();
		qx.pop();qy.pop();
		if(c[nx][ny] == '='){
			cout << res[nx][ny] + 1;
			exit(0);
		}
		if('A' <= c[nx][ny] && c[nx][ny] <= 'Z'){
			int kx,ky;
			for(int i = 1;i <= n;i++){
				for(int j = 1;j <= m;j++){
					if((nx != i || ny != j) && c[i][j] == c[nx][ny]){
						kx = i;
						ky = j;
					}
				}
			}
			nx = kx;
			ny = ky;
		}
		for(int i = 0;i < 4;i++){
			int xx = nx + dx[i];
			int yy = ny + dy[i];
			if(!vis[xx][yy] && check(xx,yy) && c[xx][yy] != '#'){
				vis[xx][yy] = 1;
				res[xx][yy] = res[nx][ny] + 1;
				qx.push(xx);
				qy.push(yy);
			}
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++){
			cin >> c[i][j];
			if(c[i][j] == '@'){
				sx = i;
				sy = j;
			}
			else if(c[i][j] == '='){
				ex = i;
				ey = j;
			}
		}
	bfs(sx,sy);
	return 0;
}
2022/8/8 11:36
加载中...