Pagini recente » Cod sursa (job #354230) | Cod sursa (job #415565) | Cod sursa (job #1007694) | Cod sursa (job #2578619) | Cod sursa (job #1501286)
#include <bits/stdc++.h>
using namespace std;
int n, m, xs, ys, xf, yf;
int a[505][505], b[505][505];
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
struct Coord
{
int x, y, cost;
};
queue <Coord> q;
bool ok(int i, int j)
{
if(i > 0 && j > 0 && i <= n && j <= m) return 1;
return 0;
}
void Read()
{
int i, j;
ifstream fin("car.in");
fin >> n >> m;
fin >> xs >> ys >> xf >> yf;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
fin >> a[i][j];
fin.close();
}
inline void Lee(int xs, int ys)
{
int i, j, k, x, y;
Coord w, w1;
w.x = xs;
w.y = ys;
w.cost = 0;
q.push(w);
b[xs][ys] = 0;
while(!q.empty())
{
w = q.front();
x = w.x;
y = w.y;
q.pop();
for(k = 0; k < 8; k++)
{
i = x + dx[k];
j = y + dy[k];
if(ok(i, j) && a[i][j] == 0 && (b[i][j] > b[x][y] + w1.cost || b[i][j] == 0 ))
{
if(k == 1 || k == 7) w1.cost = 1;
else if(k == 2 || k == 6) w1.cost = 2;
else if(k == 3 || k == 5) w1.cost = 3;
else if(k == 4) w1.cost = 4;
else if (k == 0) w1.cost = 0;
b[i][j] = b[x][y]+ w1.cost;
w1.x = i;
w1.y = j;
q.push(w1);
}
}
}
}
int main()
{
Read();
Lee(xs, ys);
ofstream fout("car.out");
fout<<b[xf][yf]-b[xs][ys];
/*for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
fout << b[i][j] << " ";
fout << endl;
}*/
fout.close();
return 0;
}