295222026-06-11 10:50:21KristófLegközelebbi szigetek **cpp17Elfogadva 100/1008ms768 KiB
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct ans
{
int a,b,dist;
};

int n,m;
vector<vector<int>> grid;

bool valid(int x,int y)
{
if(x<0 || x>=n)return false;
if(y<0 || y>=m)return false;
return true;
}

int INF=1e9;
vector<pair<int,int>> dir={{0,1},{0,-1},{1,0},{-1,0}};

ans BFS(int type)
{
queue<ans> q;
vector<vector<bool>> vis(n,vector<bool> (m,false));
for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
        if(grid[i][j]==type){q.push({i,j,0});vis[i][j]=true;}

while(q.size())
    {
    auto [x,y,dist]=q.front();q.pop();
    for(auto[dx,dy]:dir)
        {
        int nx=x+dx,ny=y+dy;

        if(!valid(nx,ny))continue;

        if(vis[nx][ny])continue;

        if(grid[nx][ny]!=type && grid[nx][ny]!=0){return {type,grid[nx][ny],dist+1};}
        q.push({nx,ny,dist+1});
        vis[nx][ny]=true;
        }
    }
return {0,0,INF};
}



int main()
{
    //freopen("be2.txt","r",stdin);
    int k;
    cin>>n>>m>>k;
    grid.resize(n,vector<int> (m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>grid[i][j];
    vector<int> vistypes(k+1,0);
    ans best={0,0,INF};
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            {
            if(!grid[i][j])continue;
            if(!vistypes[grid[i][j]])
                {
                ans tmp=BFS(grid[i][j]);
                vistypes[grid[i][j]]=true;
                if(tmp.dist<best.dist)best=tmp;
                }
            }
    cout<<best.a<<" "<<best.b;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva6/61ms500 KiB
2Elfogadva6/61ms316 KiB
3Elfogadva6/61ms316 KiB
4Elfogadva6/61ms316 KiB
5Elfogadva6/61ms316 KiB
6Elfogadva7/71ms316 KiB
7Elfogadva7/71ms316 KiB
8Elfogadva7/73ms316 KiB
9Elfogadva7/73ms508 KiB
10Elfogadva7/73ms316 KiB
11Elfogadva7/74ms316 KiB
12Elfogadva7/74ms440 KiB
13Elfogadva7/78ms560 KiB
14Elfogadva7/77ms768 KiB
15Elfogadva7/77ms452 KiB