QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #470838 | #6398. Puzzle: Tapa | UESTC_Snow_Halation# | WA | 0ms | 3708kb | C++14 | 3.3kb | 2024-07-10 16:39:42 | 2024-07-10 16:39:43 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 107;
int n, m;
string S[N];
int mp[N][N], cnt;
int timeq, dfn[N * N], match[N * N];
vector<int> g[N];
int tag[N * N];
bool dfs(int u)
{
for (int v : g[u])
{
if (dfn[v] == timeq)
continue;
dfn[v] = timeq;
if (!match[v] || dfs(match[v]))
{
match[v] = u;
return true;
}
}
return false;
}
const int dx[4] = {0, 1, 0, -1},
dy[4] = {1, 0, -1, 0};
bool check(int i, int j)
{
return ((i / 2) & 1) ^ ((j / 2) & 1);
}
int main()
{
// ios::sync_with_stdio(false);
cin >> n >> m;
n--, m--;
for (int i = 0; i <= 2 * n; i++)
cin >> S[i];
for (int i = 0; i <= 2 * n; i += 2)
for (int j = 0; j <= 2 * m; j += 2)
{
mp[i][j] = ++cnt;
if ((!i || i == 2 * n) && (!j || j == 2 * m) && S[i][j] == '2')
tag[cnt] = 1;
else if ((!i || !j || i == 2 * n || j == 2 * m) && S[i][j] == '4')
tag[cnt] = 2;
else if (S[i][j] == '7')
tag[cnt] = 3;
}
// for (int i = 1; i <= cnt; i++)
// cout << tag[i] << " ";
// cout << endl;
// return 0;
int w = 0;
for (int i = 0; i <= 2 * n; i += 2)
for (int j = 0; j <= 2 * m; j += 2)
w += (check(i, j) > 0 ? 1 : -1) * (tag[mp[i][j]] > 0);
if (w)
{
cout << "NO";
return 0;
}
for (int i = 0; i <= 2 * n; i += 2)
for (int j = 0; j <= 2 * m; j += 2)
{
if (check(i, j) || !tag[mp[i][j]])
continue;
for (int k = 0; k < 4; k++)
{
int xx = i + 2 * dx[k],
yy = j + 2 * dy[k];
if (xx < 0 || xx > 2 * n || yy < 0 || yy > 2 * m || !tag[mp[xx][yy]])
continue;
if ((tag[mp[i][j]] == 3) ^ (tag[mp[xx][yy]] != 3))
g[mp[i][j]].push_back(mp[xx][yy]);
}
}
for (int i = 0; i <= 2 * n; i += 2)
for (int j = 0; j <= 2 * m; j += 2)
{
if (check(i, j) || !tag[mp[i][j]])
continue;
timeq++;
if (!dfs(mp[i][j]))
{
cout << "NO";
return 0;
}
}
cout << "YES\n";
for (int i = 0; i <= 2 * n; i += 2)
for (int j = 0; j <= 2 * m; j += 2)
if (check(i, j) && tag[mp[i][j]])
{
const int &ret = mp[i][j];
if (ret - 1 == match[ret])
S[i][j - 1] = '!';
else if (ret + 1 == match[ret])
S[i][j + 1] = '!';
else if (ret + m + 1 == match[ret])
S[i + 1][j] = '!';
else
S[i - 1][j] = '!';
}
for (int i = 0; i <= 2 * n; i++)
for (int j = 0; j <= 2 * m; j++)
if (S[i][j] == '!')
S[i][j] = '.';
else if (S[i][j] == '.')
S[i][j] = '#';
// cout << "!!!" ;
for (int i = 0; i <= 2 * n; i++)
cout << S[i] << endl;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
3 3 2.4.3 ..... 5.8.5 ..... 3.5.3
output:
YES 2.4#3 ##### 5#8#5 ##### 3#5#3
result:
ok Correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
3 3 3.4.3 ..... 5.7.5 ..... 3.5.3
output:
NO
result:
ok Correct.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 2 2.2 ... 2.2
output:
YES 2.2 ### 2.2
result:
ok Correct.
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3708kb
input:
2 50 2.4.4.4.4.5.5.5.5.5.5.5.5.4.5.5.4.4.5.5.5.5.4.5.5.5.5.5.4.4.5.4.5.5.5.5.5.5.5.5.5.5.5.4.4.5.5.4.5.3 ................................................................................................... 2.5.5.4.4.5.5.5.4.4.5.5.5.4.5.5.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.4.4.4.5.5.5.5.5.5.5.4.4.5.5.5.5.4...
output:
YES 2#4.4#4.4#5#5#5#5#5#5#5#5#4#5#5#4.4#5#5#5#5#4#5#5#5#5#5#4.4#5#4#5#5#5#5#5#5#5#5#5#5#5#4.4#5#5#4#5#3 .#########################.#################.#################.###############################.#### 2#5#5#4.4#5#5#5#4.4#5#5#5#4#5#5#5#5#5#5#5#5#4#4.4#5#5#5#5#5#5#4#4.4#5#5#5#5#5#5#5#4.4#5#5#5#5#4#...
result:
wrong answer Clue not satisfied at (1,27), non-consecutive shaded cells