Cod sursa(job #1263911)

Utilizator Narcys01Ciovnicu Narcis Narcys01 Data 15 noiembrie 2014 11:34:49
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <fstream>

using namespace std;

int a[1055][1055], n;
int b[1055][1055];

int dx[] = { 0, 0,-1, 1};
int dy[] = {-1, 1, 0, 0};

struct coda
{
    int x, y, m;
} w, w1, q[1055 * 1055];

void Citire()
{
    ifstream fin("alpin.in");
    int i, j;
    fin >> n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            fin >> a[i][j];
    for (i = 0; i <= n + 1; i++)
        a[0][i] = a[i][0] = a[n+1][i] = a[i][n+1] = -1;
}

void Afisare()
{
    int i, j, vma, l, c;
    vma = -1;
    l = c = 1;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (vma < b[i][j])
            {
                l = i;
                c = j;
                vma = b[i][j];
            }
    ofstream fout("alpin.out");
    fout << vma << "\n";
    while (vma > 0)
    {
        fout << l << " " << c << "\n";
        for (i = 0; i < 4; i++)
            if (b[l][c] - 1 == b[l+dx[i]][c+dy[i]])
            {
                l = l + dx[i];
                c = c + dy[i];
                i = 8;
            }
        vma--;
    }
}

void Lee()
{
    int pr, ul, k, i, j;
    pr = 0;
    ul = -1;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
        {
            k = 4;
            /*for (k = 0; k < 4; k++)
                if (a[i][j] <= a[i+dx[k]][j+dy[k]])
                    break;*/
            if (k == 4)
            {
                ul++;
                b[i][j] = 1;
                q[ul].x = i;
                q[ul].m = 1;
                q[ul].y = j;
            }
        }
    while (pr <= ul)
    {
        w = q[pr];
        pr++;
        for (k = 0; k < 4; k++)
        {
            w1.x = w.x + dx[k];
            w1.y = w.y + dy[k];
            w1.m = w.m + 1;
            if (a[w1.x][w1.y] != -1 && a[w1.x][w1.y] < a[w.x][w.y] &&
                (!b[w1.x][w1.y] || b[w1.x][w1.y] < w1.m))
            {
                ul++;
                q[ul] = w1;
                b[w1.x][w1.y] = w1.m;
            }
        }
    }
}

int main()
{
    Citire();
    Lee();
    Afisare();
    return 0;
}