Pagini recente » Monitorul de evaluare | Profil beji | Istoria paginii utilizator/macarescu | Istoria paginii utilizator/bogoo | Cod sursa (job #2498049)
#include <bits/stdc++.h>
using namespace std;
ifstream f("padure.in");
ofstream g("padure.out");
int n,m,xstart,ystart,xfinish,yfinish;
int a[1001][1001];
int drum[1001][1001];
bool viz[1001][1001];
struct Node
{
int x;
int y;
};
int x_path[] = {0,0,1,-1};
int y_path[] = {1,-1,0,0};
bool is_ok(int x,int y)
{
return(x>=1 && y>=1 && x<=n && y<=m && viz[x][y] == false);
}
int Lee()
{
deque<Node> dq;
dq.push_back({xstart,ystart});
viz[xstart][ystart] = true;
drum[xstart][ystart] = 0;
while(!dq.empty())
{
Node prim = dq.front();
dq.pop_front();
viz[prim.x][prim.y] = true;
for(int k=0;k<4;++k)
{
int x_next = prim.x + x_path[k];
int y_next = prim.y + y_path[k];
if(is_ok(x_next,y_next))
{
if(a[x_next][y_next] == a[prim.x][prim.y])
{
dq.push_front({x_next,y_next});
drum[x_next][y_next] = min(drum[prim.x][prim.y],drum[x_next][y_next]);
}
else
{
dq.push_back({x_next,y_next});
drum[x_next][y_next] = min(drum[prim.x][prim.y] + 1, drum[x_next][y_next]);
}
}
}
}
}
int main()
{
f>>n>>m>>xstart>>ystart>>xfinish>>yfinish;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
f>>a[i][j];
drum[i][j] = INFINITY;
}
Lee();
g<<drum[xfinish][yfinish];
return 0;
}