QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135468 | #6394. Turn on the Light | UrgantTeam# | RE | 0ms | 0kb | C++23 | 4.2kb | 2023-08-05 15:53:17 | 2023-08-05 15:53:21 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long ll;
char matr[105][105];
int alive[105][105];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int sosx[4] = {-2, 0, 2, 0}, sosy[4] = {0, 2, 0, -2};
vector <int> g[10005];
bool used[10005];
int pairL[10005], pairR[10005];
bool dfs(int v)
{
used[v] = true;
for (int u : g[v])
{
if (pairR[u] == 0)
{
pairL[v] = u, pairR[u] = v;
return true;
}
if (!used[pairR[u]] && dfs(pairR[u]))
{
pairL[v] = u, pairR[u] = v;
return true;
}
}
return false;
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= 2 * n - 1; i++)
for (int j = 1; j <= 2 * m - 1; j++)
cin >> matr[i][j];
int quant = 0;
for (int i = 1; i <= 2 * n - 1; i++)
for (int j = 1; j <= 2 * m - 1; j++)
{
if (i % 2 == 1 && j % 2 == 1)
{
int fr = 0;
for (int k = 0; k < 8; k++)
{
int nx = i + dx[k], ny = j + dy[k];
if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1) fr++;
}
if (fr == matr[i][j] - '0') continue;
alive[i][j] = ++quant;
}
else matr[i][j] = '#';
}
for (int i = 1; i <= 2 * n - 1; i++)
for (int j = 1; j <= 2 * m - 1; j++)
{
if (alive[i][j] != 0)
{
int sos = 0;
for (int k = 0; k < 4; k++)
{
int nx = i + sosx[k], ny = j + sosy[k];
if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1) sos++;
}
if (sos == 2 || sos == 4)
{
for (int k = 0; k < 4; k++)
{
int nx = i + sosx[k], ny = j + sosy[k];
if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1 && alive[nx][ny] != 0 && mp(i, j) < mp(nx, ny))
{
g[alive[i][j]].pb(alive[nx][ny]);
g[alive[nx][ny]].pb(alive[i][j]);
}
}
}
if (sos == 3)
{
pair <int, int> rev;
for (int k = 0; k < 4; k++)
{
int nx = i + sosx[k], ny = j + sosy[k];
if (!(1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1)) rev = mp(-sosx[k], -sosy[k]);
}
for (int k = 0; k < 4; k++)
{
int nx = i + sosx[k], ny = j + sosy[k];
if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1 && alive[nx][ny] != 0 && mp(i, j) < mp(nx, ny) &&
mp(sosx[k], sosy[k]) != rev)
{
g[alive[i][j]].pb(alive[nx][ny]);
g[alive[nx][ny]].pb(alive[i][j]);
}
}
}
}
}
if (quant % 2 == 1) cout << "NO\n", exit(0);
vector <int> lefts;
for (int i = 1; i <= 2 * n - 1; i++)
for (int j = 1; j <= 2 * m - 1; j++)
if (alive[i][j] != 0 && (i + j) % 4 == 2) lefts.pb(alive[i][j]);
if ((int) lefts.size() != quant / 2) cout << "NO\n", exit(0);
bool fl = true;
int match = 0;
while (fl)
{
fl = false;
for (int v : lefts) used[v] = false;
for (int v : lefts)
if (!used[v] && pairL[v] == 0 && dfs(v))
{
match++;
fl = true;
}
}
if (match != (int) lefts.size()) cout << "NO\n", exit(0);
cout << "YES\n";
for (int i = 1; i <= 2 * n - 1; i++)
for (int j = 1; j <= 2 * m - 1; j++)
{
if (alive[i][j] != 0) continue;
if ((i + j) % 4 != 2) continue;
int sos = pairL[alive[i][j]];
for (int k = 0; k < 4; k++)
{
int nx = i + sosx[k], ny = j + sosy[k];
if (1 <= nx && nx <= 2 * n - 1 && 1 <= ny && ny <= 2 * m - 1 && alive[nx][ny] == sos)
{
matr[i + sosx[k] / 2][j + sosy[k] / 2] = '.';
}
}
}
for (int i = 1; i <= 2 * n - 1; i++)
{
for (int j = 1; j <= 2 * m - 1; j++)
cout << matr[i][j];
cout << '\n';
}
return 0;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
3