Cod sursa(job #1908311)

Utilizator savigunFeleaga Dragos-George savigun Data 7 martie 2017 00:29:43
Problema Algoritmul Bellman-Ford Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

struct Cell { int x, y; };

int n, m, sx, sy, fx, fy;
Cell q[60000000];
int a[1001][1001], d[1001][1001];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 1e7;

void citire();
void afisare();


int main() {
    citire();

    int p = 1, u = 1;
    Cell c;
    c.x = sx;
    c.y = sy;
    d[sx][sy] = 0;
    q[u] = c;

    while (p <= u) {
        c = q[p];
        for (int k = 0; k < 4; ++k) {
            int i = c.x + dx[k];
            int j = c.y + dy[k];
            if (i >= 1 && i <= n && j >= 1 && j <= m) {
                int diamonds = d[c.x][c.y];
                if (a[i][j] != a[c.x][c.y]) diamonds++;
                if (d[i][j] > diamonds) {
                    d[i][j] = diamonds;
                    Cell c2; c2.x = i; c2.y = j;
                    q[++u] = c2;
                }
            }
        }
        p++;
    }

    afisare();


    return 0;
}




void afisare() {
    ofstream out("padure.out");

    out << d[fx][fy];

    out.close();
}

void citire() {
    ifstream in("padure.in");
    in >> n >> m >> sx >> sy >> fx >> fy;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            in >> a[i][j];
            d[i][j] = INF;
        }
    }

    in.close();
}