20分求调
查看原帖
20分求调
1137394
Hyvial楼主2024/4/21 15:58

题目 为什么MLE了8 个点啊!

#include <bits/stdc++.h>
#define LL long long
#define DB double
#define BUG cout << "OoO" << endl

using namespace std;

const int N = 30;
char mp[N][N];
bool vis[N][N][N][N];
int n, m, Ax, Ay, Bx, By, Zx, Zy, ans;
int dx[2][4] = {{1, -1, 0, 0}, {1, -1, 0, 0}}, dy[2][4] = {{0, 0, -1, 1}, {0, 0, 1, -1}};

struct Node{int ax, ay, bx, by, t;};
queue <Node> q;

void bfs()
{
	vis[Ax][Ay][Bx][By] = 1;
	q.push(Node{Ax, Ay, Bx, By, 0});
	
	while(!q.empty())
	{
		Node u = q.front();
		q.pop();
		
		for(int i = 0; i < 4; i ++ )
		{
			Node v;
			v.ax = u.ax + dx[0][i];
			v.bx = u.bx + dx[1][i];
			v.ay = u.ay + dy[0][i];
			v.by = u.by + dy[1][i];
			v.t = u.t + 1;
			
			if(v.ax < 1 || v.ax > n || v.ay < 1 || v.ay > m) continue;
			if(v.bx < 1 || v.bx > n || v.by < 1 || v.by > m) continue;
			if(mp[v.ax][v.ay] == 'X' || mp[v.bx][v.by] == 'X') continue;
			if(mp[v.ax][v.ay] == '#') v.ax -= dx[0][i], v.ay -= dy[0][i];
			if(mp[v.bx][v.by] == '#') v.bx -= dx[1][i], v.by -= dy[1][i]; 
			
			if(v.ax == v.bx && v.bx == Zx && v.ay == v.by && v.by == Zy)
			{
				printf("%d", u.t + 1);
				return ;
			}
			q.push(v);
			vis[v.ax][v.ay][v.bx][v.by] = 1;
		}
	}
	
	printf("no");
	return ;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++ )
	{
		for(int j = 1; j <= m; j ++ )
		{
			cin >> mp[i][j];
			if(mp[i][j] == 'G') Ax = i, Ay = j;
			if(mp[i][j] == 'M') Bx = i, By = j;
			if(mp[i][j] == 'T') Zx = i, Zy = j;
		}
	}
	
	bfs();
	
    return 0;
}

2024/4/21 15:58
加载中...