Pagini recente » Cod sursa (job #2163828) | Cod sursa (job #360771) | Cod sursa (job #3275403) | Cod sursa (job #705126) | Cod sursa (job #2940395)
#include <iostream>
using namespace std;
int mat[1005][1005];
int din[1005][1005];
int ver[1005][1005];
int f[1005][1005];
pair<int,int> dir[4]= {{-1,0},{0,1},{1,0},{0,-1}};
deque <pair<int,int>> d;
void mubfs()
{
while(d.size())
{
int i,j;
tie(i,j)=d.back();
for(int k=0;k<4;k++)
{
int x=i+dir[k].first,y=j+dir[k].second;
if(!f[x][y])
d.push_back({x,y});
}
}
}
int main()
{
int n,m;
fin>>n>>m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
char ch;
cin>>ch;
if(ch=='*')
mat[i][j]=1;
d.push_back((i-1)*m+j);
}
}
mubfs();
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
int minn=1e9;
for(int l=0;l<4;l++)
{
int x=dir[l].first+i,y=dir[l].second+j;
if(!mat[x][y])
minn=min(minn,din[x][y]);
}
din[i][j]=minn+ver[i][j];
}
}
return 0;
}