Cod sursa(job #1041877)

Utilizator vladm97Matei Vlad vladm97 Data 26 noiembrie 2013 12:32:03
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include<iostream>
#include<fstream>
#include<vector>
#include <queue>

using namespace std;

int n,m;
short int h;
int count;
int input[1010][1010];
bool parcurs[1010][1010];
ifstream in("tsunami.in");
ofstream out("tsunami.out");

struct pos
{
    int i;
    int j;
}a;
vector <pos> startPos;
queue <pos> myQueue;
void read()
{
    in>>n>>m>>h;
    int x;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m;j++)
        {
            in>>x;
            input[i][j] = x;
            if(x == 0)
            {
                a.i = i;
                a.j = j;
                startPos.push_back(a);
            }
        }
    }
}

void queueUp(int i, int j)
{
    i--;
    a.i = i;
    if(parcurs[i][j] == false && h > input[i][j] && input[i][j] > 0)
    {
        a.j = j;
        myQueue.push(a);
    }
}

void queueMiddle(int i, int j)
{
    a.i = i;
    if(parcurs[i][j-1] == false && h > input[i][j-1] && input[i][j-1] > 0)
    {
        a.j = j-1;
        myQueue.push(a);
    }
    if(parcurs[i][j+1] == false && h  > input[i][j+1] && input[i][j+1] > 0)
    {
        a.j = j+1;
        myQueue.push(a);
    }
}

void queueDown(int i, int j)
{
    i++;
    a.i = i;
    if(parcurs[i][j] == false && h > input[i][j] && input[i][j] > 0)
    {
        a.j = j;
        myQueue.push(a);
    }
}

void queueMyNeighbours(int i, int j)
{
    queueUp(i,j);
    queueMiddle(i,j);
    queueDown(i,j);
}

void bfs(pos A)
{
    pos aux;
    int c1,c2;
    int i,j;
    myQueue.push(A);
    while(myQueue.empty() == false)
    {
        count++;
        aux = myQueue.front();
        myQueue.pop();
        queueMyNeighbours(aux.i,aux.j);
        parcurs[aux.i][aux.j] = true;
    }
}

void startAll()
{
    pos a;
    for(int i = 0; i<startPos.size(); i++)
    {
        a = startPos[i];
        bfs(a);
    }
    count -= startPos.size();
}

void write()
{
    out<<count;
}

int main()
{
    read();
    startAll();
    write();
}