Pagini recente » Cod sursa (job #3139206) | Cod sursa (job #30913) | Cod sursa (job #2217416) | Cod sursa (job #2328050) | Cod sursa (job #2868821)
#include <fstream>
#include <queue>
#define nmax 101
using namespace std;
ifstream cin ("lacuri.in");
ofstream cout ("lacuri.out");
int n, mat[nmax + 1][nmax + 1], c[nmax + 1][nmax + 1], dirx[] = {1, -1, 0, 0}, diry[] = {0, 0, 1, -1}, len, ok, sx, sy, cn;
pair<int, int> memo[nmax + 1][nmax + 1], sol[nmax * nmax + 1];
queue<pair<int, int>> q;
void dfs (int x, int y)
{
for (int i = 0; i < 4; i++)
if (c[x + dirx[i]][y + diry[i]] == 1)
c[x + dirx[i]][y + diry[i]] = 0, dfs (x + dirx[i], y + diry[i]);
if (! (x >= sx && x <= sx + len - 1 && y >= sy && y <= sy + len - 1))
ok = 1;
else
cn++;
}
void bfs()
{
int x, y, ax, ay, i;
q.push ({1, 1});
memo[1][1] = {1, 1};
mat[1][1] = 1;
while (!q.empty())
{
x = q.front().first, y = q.front().second;
q.pop();
for (i = 0; i < 4; i++)
{
ax = x + dirx[i], ay = y + diry[i];
if (ax >= 1 && ay >= 1 && ax <= n && ay <= n && mat[ax][ay] == 0)
{
mat[ax][ay] = 1;
memo[ax][ay] = {x, y};
q.push ({ax, ay});
}
}
}
}
int main()
{
int cnt = 0, i, j, col, tot = 0, p = 0;
pair<int, int> x;
cin >> n;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
cin >> mat[i][j], c[i][j] = mat[i][j];
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (c[i][j] == 1)
{
tot++;
ok = 0, len = 0;
for (col = j; col <= n && c[i][col] == 1; col++)
len++;
c[i][j] = 0;
sx = i, sy = j, cn = 0;
dfs (i, j);
if (ok == 0 && cn == len * len)
cnt++;
}
cout << cnt << '\n';
if (cnt == tot && (! (cnt == 1 && mat[1][1] == 1)))
{
bfs();
x.first = x.second = n;
while (x.first != 1 || x.second != 1)
{
sol[++p] = x;
x = memo[x.first][x.second];
}
cout << 1 << " " << 1 << '\n';
for (i = p; i >= 1; i--)
cout << sol[i].first << " " << sol[i].second << '\n';
}
return 0;
}