Pagini recente » Cod sursa (job #1132489) | Cod sursa (job #184461) | Cod sursa (job #2017717) | Cod sursa (job #1175754) | Cod sursa (job #1565982)
#include <fstream>
#include <queue>
using namespace std;
deque < pair <int, int> > q;
int n,w,m,z,t,c,d,i,j,x,y,k,b[1005][1005],v[1005][1005];
int main()
{
ifstream f("padure.in");
ofstream g("padure.out");
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
f>>n>>m;
f>>z>>t>>c>>d;
q.push_back(make_pair(z,t));
for(i=1; i<=n; i++)
for(j=1; j<=m; j++)
{
f>>v[i][j];
b[i][j]=9000005;
}
b[z][t]=0;
for(i=0; i<=n+1; i++)
{
b[i][0]=-1;
b[i][m+1]=-1;
}
for(i=0; i<=m+1; i++)
{
b[i][0]=-1;
b[i][n+1]=-1;
}
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop_front();
for(k=0; k<4; k++)
{
x=i+dx[k];
y=j+dy[k];
if(v[x][y]==v[i][j]&&b[x][y]>b[i][j])
{
w = b[x][y]=b[i][j];
if (!q.empty() && w <= b[q.front().first][q.front().second])
q.push_front(make_pair(x,y));
else q.push_back(make_pair(x,y));
}
else
if(b[x][y]>b[i][j]+1)
{
w = b[x][y]=b[i][j]+1;
if (!q.empty() && w <= b[q.front().first][q.front().second])
q.push_front(make_pair(x,y));
else q.push_back(make_pair(x,y));
}
}
}
g<<b[c][d]<<'\n';
f.close(); g.close();
return 0;
}