Pagini recente » Cod sursa (job #1133013) | Cod sursa (job #1434643) | Cod sursa (job #1937058) | Cod sursa (job #395114) | Cod sursa (job #2667560)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("padure.in");
ofstream g("padure.out");
int n, m, padure[1001][1001], cost[1001][1001];
struct punct { int linie, coloana; }printul, castel;
queue<punct> coada;
void citire() {
f>>n>>m;
f>>printul.linie>>printul.coloana;
f>>castel.linie>>castel.coloana;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
f>>padure[i][j];
cost[i][j] = -1;
}
}
void dfs(punct p, int c) {
//cout<<"DFS-> "<<p.linie<<' '<<p.coloana<<" = "<<c<<endl;
coada.push(p);
cost[p.linie][p.coloana] = c;
punct a1, a2, a3, a4;
a1.linie = p.linie+1;
a1.coloana = p.coloana;
a2.linie = p.linie;
a2.coloana = p.coloana+1;
a3.linie = p.linie-1;
a3.coloana = p.coloana;
a4.linie = p.linie;
a4.coloana = p.coloana-1;
if(padure[p.linie][p.coloana] == padure[a1.linie][a1.coloana]
&& cost[a1.linie][a1.coloana] == -1)
{
cost[a1.linie][a1.coloana] = cost[p.linie][p.coloana];
//cout<<"A ";
dfs(a1, c);
}
if(padure[p.linie][p.coloana] == padure[a2.linie][a2.coloana]
&& cost[a2.linie][a2.coloana] == -1)
{
cost[a2.linie][a2.coloana] = cost[p.linie][p.coloana];
//cout<<"B ";
dfs(a2, c);
}
if(padure[p.linie][p.coloana] == padure[a3.linie][a3.coloana]
&& cost[a3.linie][a3.coloana] == -1)
{
cost[a3.linie][a3.coloana] = cost[p.linie][p.coloana];
//cout<<"C ";
dfs(a3, c);
}
if(padure[p.linie][p.coloana] == padure[a4.linie][a4.coloana]
&& cost[a4.linie][a4.coloana] == -1)
{
cost[a4.linie][a4.coloana] = cost[p.linie][p.coloana];
//cout<<"D ";
dfs(a4, c);
}
}
void bfs(punct p) {
dfs(p, 0);
punct x;
while(!coada.empty()) {
//cout<<"\n: ";
x = coada.front();
coada.pop();
//cout<<x.linie<<' '<<x.coloana<<' ';
punct a1, a2, a3, a4;
a1.linie = x.linie+1;
a1.coloana = x.coloana;
//cout<<"\n -> "<<a1.linie<<' '<<a1.coloana<<" = "<<cost[a1.linie][a1.coloana]<<endl;
a2.linie = x.linie;
a2.coloana = x.coloana+1;
a3.linie = x.linie-1;
a3.coloana = x.coloana;
a4.linie = x.linie;
a4.coloana = x.coloana-1;
if(cost[a1.linie][a1.coloana] == -1)
dfs(a1, cost[x.linie][x.coloana] + 1);
if(cost[a2.linie][a2.coloana] == -1)
dfs(a2, cost[x.linie][x.coloana] + 1);
if(cost[a3.linie][a3.coloana] == -1)
dfs(a3, cost[x.linie][x.coloana] + 1);
if(cost[a4.linie][a4.coloana] == -1)
dfs(a4, cost[x.linie][x.coloana] + 1);
}
}
int main() {
citire();
bfs(printul);
// cout<<endl;
// for(int i=1; i<=n; i++){
// for(int j=1; j<=m; j++)
// cout<<cost[i][j]<<' ';
// cout<<'\n';
// }
//
// cout<<"________________";
// cout<<endl;
// for(int i=1; i<=n; i++){
// for(int j=1; j<=m; j++)
// cout<<padure[i][j]<<' ';
// cout<<'\n';
// }
g<<cost[castel.linie][castel.coloana];
}