QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561779 | #6398. Puzzle: Tapa | chimera | WA | 0ms | 3864kb | C++17 | 1.9kb | 2024-09-13 10:20:18 | 2024-09-13 10:20:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
ll N,M;
bool valid(ll x, ll y) {
return (0 <= x) && (x < 2*N-1) && (0 <= y) && (y < 2*M-1);
}
bool edge(ll x, ll y) {
return (x == 0) || (x == 2*N-2) || (y == 0) || (y == 2*M-2);
}
vector<pll> adjs(ll x, ll y) {
vector<pll> chk = {{x+2,y},{x-2,y},{x,y+2},{x,y-2}};
vector<pll> out = {};
for(auto c: chk) if(valid(c.first,c.second) && (edge(x,y) == edge(c.first,c.second))) out.push_back(c);
return out;
}
bool small(char x) {
return x == '2' || x == '4' || x == '7';
}
int main() {
cin >> N >> M;
vector<string> grid(2*N-1);
for(ll i = 0; i < 2*N-1; i++) { cin >> grid[i]; for(auto& x: grid[i]) if(x == '.') x='#';}
vector<vector<bool>> matched(2*N-1, vector<bool>(2*M-1,false));
while(true) {
pll mxy;
ll nxya = 100;
for(ll i = 0; i < grid.size(); i += 2) {
for(ll j = 0; j < grid[0].size(); j += 2) {
if(matched[i][j]) continue;
if(!small(grid[i][j])) continue;
ll na = 0;
for(auto a: adjs(i,j)) if(small(grid[a.first][a.second]) && !matched[a.first][a.second]) na++;
if(na < nxya) {
mxy = {i,j};
nxya = na;
}
}
}
if(nxya == 100) break;
if(nxya == 0) {
cout << "NO\n"; return 0;
}
for(auto a: adjs(mxy.first,mxy.second)) {
if(small(grid[a.first][a.second]) && !matched[a.first][a.second]) {
matched[mxy.first][mxy.second]=true;
matched[a.first][a.second]=true;
grid[(mxy.first+a.first)/2][(mxy.second+a.second)/2]='.';
break;
}
}
}
cout << "YES\n";
for(auto x: grid) cout << x << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3520kb
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: 3668kb
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: 3632kb
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: 3864kb
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,7), non-consecutive shaded cells