Pagini recente » Cod sursa (job #3218660) | Cod sursa (job #3206601) | Cod sursa (job #2635982) | Cod sursa (job #706244) | Cod sursa (job #1263911)
#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;
}