竞赛讨论区 > 小喵觅食数据可能有误
头像
Eriktse
发布于 11-18 21:09 湖北
+ 关注

小喵觅食数据可能有误

当r1 = 1, r2 = 1,地图为"MP"时,一行两列,没有'.'和'*'时,此时找不到空地作为中转点,但是显然可以吃到鱼干,距离为1。

但是我的代码如下是无法通过的,当68行增加判断mp[i][j] == '.'后方可通过。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e3 + 9, inf = 2e18;

int d1[maxn][maxn], d2[maxn][maxn], n, m, r1, r2;
char mp[maxn][maxn];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

bool inmp(int x, int y){return 1 <= x && x <= n && 1 <= y && y <= m;}

void bfs(int sx, int sy, int d[][maxn])
{
	queue<pair<int, int> > q;
	bitset<maxn> vis[maxn];
	vis[sx][sy] = true;
	d[sx][sy] = 0;
	q.push({sx, sy});
	
	while(!q.empty())
	{
		int x = q.front().first, y = q.front().second;
		q.pop();
		
		for(int i = 0;i < 4; ++ i)
		{
			int nx = x + dx[i], ny = y + dy[i];
			
			if(!inmp(nx, ny) || vis[nx][ny] || mp[nx][ny] == '*')continue;
			
			d[nx][ny] = d[x][y] + 1;
			vis[nx][ny] = true;
			q.push({nx, ny});
		}	
	}
}

int getabs(int x){return x < 0 ? -x : x;}

int dis(int x1, int y1, int x2, int y2)
{
	return getabs(x1 - x2) + getabs(y1 - y2);
}

signed main()
{
	scanf("%lld %lld %lld %lld", &n, &m, &r1, &r2);
	for(int i = 1;i <= n; ++ i)scanf("%s", mp[i] + 1);	
	
	int x1, y1, x2, y2;//1是PLMM,2是猫
	
	for(int i = 1;i <= n; ++ i)
		for(int j = 1;j <= m; ++ j)
		{
			d1[i][j] = d2[i][j] = 2 * inf;

			if(mp[i][j] == 'P')x1 = i, y1 = j;
			else if(mp[i][j] == 'M')x2 = i, y2 = j;
		}
	bfs(x1, y1, d1);
	bfs(x2, y2, d2);
	
	int ans = inf;
	for(int i = 1;i <= n; ++ i)
		for(int j = 1;j <= m; ++ j)
		{	
			if(dis(i, j, x1, y1) <= r1 && dis(i, j, x2, y2) <= r2)//增加判断条件mp[i][j] == '.'即可通过
			{
				ans = min(ans, d1[i][j] + d2[i][j]);
			}
		}

	printf("%lld\n", ans == inf ? -1 : ans);
	return 0;
}

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐