Pagini recente » Cod sursa (job #497731) | Cod sursa (job #2887314) | Istoria paginii runda/simulare_oji_a_10-a/clasament | onis-2016/solutii-runda-1 | Cod sursa (job #2950164)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("alpin.in");
ofstream out ("alpin.out");
int n;
int a[1025][1025];
int dp[1025][1025];
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int dfs (int x, int y)
{
if (dp[x][y] != -1)
return dp[x][y];
dp[x][y] = 1;
for (int k=0; k<4; k++)
{
int i = x + dx[k], j = y + dy[k];
if (i > 0 && i <= n && j > 0 && j <= n && a[i][j] > a[x][y])
dp[x][y] = max(dp[x][y], dfs(i, j) + 1);
}
return dp[x][y];
}
void print (int x, int y)
{
out << x << ' ' << y << '\n';
if (dp[x][y] == 1)
return;
for (int k=0; k<4; k++)
{
int i = x + dx[k], j = y + dy[k];
if (i > 0 && j > 0 && i <= n && j <= n && dp[i][j] == dp[x][y] - 1)
{
print(i, j);
return;
}
}
}
int main()
{
in >> n;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
in >> a[i][j], dp[i][j] = -1;
}
int ans = 1;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
if (dp[i][j] == -1)
{
dfs(i, j), ans = max(ans, dp[i][j]);
}
}
}
out << ans << '\n';
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
if (dp[i][j] == ans)
{
print(i, j);
return 0;
}
}
}
return 0;
}