AcWing 5742. 夺宝大赛
原题链接
困难
作者:
shining太阳
,
2025-03-26 14:39:18
·甘肃
,
所有人可见
,
阅读 1
注意题目x,y的顺序坐标顺序反着
bfs()宽搜即可
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 105;
typedef pair<int,int> PII;
int n,m,k;
int g[N][N];
queue<PII> q;
bool st[N][N];
int dist[N][N];
int ans[210];
int cnt[210];
int ex,ey;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
void bfs(int x,int y)
{
st[x][y] = true;
dist[x][y] = 0;
q.push({x,y});
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0;i < 4;i ++ )
{
int a = t.x + dx[i];
int b = t.y + dy[i];
if(a < 1 || a > n || b < 1 || b > m || st[a][b] || g[a][b] == 0)continue;
st[a][b] = true;
dist[a][b] = min(dist[a][b],dist[t.x][t.y] + 1);
q.push({a,b});
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++ )
for(int j = 1;j <= m;j ++ )
cin >> g[i][j];
cin >> k;
for(int i = 1;i <= n;i ++ )
for(int j = 1;j <= m;j ++ )
{
if(g[i][j] == 2)
{
ex = i,ey = j;
break;
}
}
memset(dist,0x3f,sizeof dist);
bfs(ex,ey);
for(int i = 1;i <= k;i ++ )
{
int x,y;
cin >> x >> y;
if(dist[y][x] != 0x3f3f3f3f)
{
ans[dist[y][x]] = i;
cnt[dist[y][x]] ++;
}
}
for(int i = 1;i <= 205;i ++ )
{
if(cnt[i] == 1)
{
cout << ans[i] << " " << i << endl;
return 0;
}
}
cout << "No winner." << endl;
return 0;
}