Pagini recente » Cod sursa (job #653916) | Cod sursa (job #327658) | Cod sursa (job #442524) | Cod sursa (job #2954142) | Cod sursa (job #2925299)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1000;
struct Celula{
int l, c, cap;
Celula(int l, int c, int cap):l(l), c(c), cap(cap){}
Celula(){}
};
int mat[NMAX + 5][NMAX + 5];
int viz[NMAX + 5][NMAX + 5];
int dirlin[] = {-1, 0, 1, 0}, dircol[] = {0, 1, 0, -1};
bool bfs(int n, int cap, int pl, int pc, int cl, int cc) {
queue<Celula> Q;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
viz[i][j] = -1;
viz[pl][pc] = 1;
Q.push(Celula(pl, pc, cap));
while(!Q.empty()) {
auto [l, c, cap] = Q.front();
Q.pop();
for(int dir = 0; dir < 4; dir++) {
int newL = l + dirlin[dir];
int newC = c + dircol[dir];
if(newL > 0 && newL <= n && newC > 0 && newC <= n) {
if(mat[l][c] != mat[newL][newC] && !cap)
continue;
if(viz[newL][newC] < cap - (mat[l][c] != mat[newL][newC])) {
viz[newL][newC] = cap - (mat[l][c] != mat[newL][newC]);
if(newL == cl && newC == cc)
return true;
Q.push({newL, newC, cap - (mat[l][c] != mat[newL][newC])});
}
}
}
}
return false;
}
int main()
{
ifstream fin("padure.in");
ofstream fout("padure.out");
int n, m, pl, pc, cl, cc;
fin >> n >> m >> pl >> pc >> cl >> cc;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
fin >> mat[i][j];
int st = 1, dr = NMAX * NMAX;
while(st <= dr) {
int mij = (st + dr) / 2;
if(bfs(n, mij, pl, pc, cl, cc))
dr = mij - 1;
else
st = mij + 1;
}
fout << st;
fin.close();
fout.close();
return 0;
}