QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#640888 | #7733. Cool, It’s Yesterday Four Times More | Doubeecat | WA | 2ms | 3796kb | C++20 | 3.7kb | 2024-10-14 16:42:21 | 2024-10-14 16:42:25 |
Judging History
answer
/*
Undo the destiny.
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
vector <vector<int> > ma;
vector <vector<int> > vis;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {1,-1,0,0};
int n,m,col;
vector <pii> ps;
map <int,int> sta,viss;
bool valid(int x,int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void dfs1(int x,int y) {
ps.push_back(mp(x,y));
vis[x][y] = col;
for (int i = 0;i < 4;++i) {
int nx = x + dx[i],ny = y + dy[i];
if (valid(nx,ny) && !ma[nx][ny]) {
if (!vis[nx][ny]) {
dfs1(nx,ny);
}
}
}
}
int zip(pii x,pii y) {
int a,b,c,d;a = x.first,b = x.second;c = y.first,d = y.second;
return d + c * m + b * n * m + a * m * n * m;
}
pair<pii,pii> unzip(int x) {
pii a,b;
b.second = x % m;
x /= m;
b.first = x % n;
x /= n;
a.second = x % m;
x /= m;
a.first = x;
return mp(a,b);
}
void bfs(int stt) {
queue <int> q;
q.push(stt);
while (!q.empty()) {
int nowsta = q.front();q.pop();
pii s = unzip(nowsta).first,t = unzip(nowsta).second;
int xx = s.first,yy = s.second;
int xxx = t.first,yyy = t.second;
//printf("(%d,%d)-(%d,%d)\n",xx,yy,xxx,yyy);
bool flag = 0;
for (int i = 0;i < 4;++i){
int nx = xx + dx[i],ny = yy + dy[i];
int nxx = xxx + dx[i],nyy = yyy + dy[i];
if (!valid(nx,ny) || ma[nx][ny]) continue;
if (!valid(nxx,nyy) || ma[nxx][nyy]) {
sta[stt] = 1;
return ;
}
if (!sta[zip(mp(nx,ny),mp(nxx,nyy))])q.push(zip(mp(nx,ny),mp(nxx,nyy)));
if (sta[zip(mp(nx,ny),mp(nxx,nyy))] == 1) sta[nowsta] = 1,flag = 0;
}
if (!flag) sta[nowsta] = -1;
}
}
void solve() {
cin >> n >> m;
ma.clear();vis.clear();col = 0;
sta.clear();
ma.resize(n);
vis.resize(n);
int siz= 0;
for (int i = 0;i < n;++i) {
ma[i].resize(m);
vis[i].resize(m);
for (int j = 0;j < m;++j) {
char c;cin >> c;
if (c == 79) ma[i][j] = 1;
else ma[i][j] = 0,++siz;
}
}
int ans = 0;
for (int i = 0;i < n;++i) {
for (int j = 0;j < m;++j) {
if (!ma[i][j] && !vis[i][j]) {
ps.clear();
++col;
dfs1(i,j);
/*puts("newbrick");
for (auto p : ps) {
printf("(%d,%d)\n",p.first,p.second);
}*/
//sta.clear();
for (auto p1 : ps) {
int cnt = 0;
for (int xx = 0;xx < n;++xx) {
for (int yy = 0;yy < m;++yy) {
pii p2 = mp(xx,yy);
if (p2 == p1 || ma[xx][yy]) continue;
if (!sta[zip(p1,p2)]) bfs(zip(p1,p2));
if (sta[zip(p1,p2)]== 1) {
++cnt;
}
}
}
if (cnt == siz - 1) {
++ans;
}
}
}
}
}
cout << ans << "\n";
}
signed main() {
//ios::sync_with_stdio(false);
//cin.tie(0);//cout.tie(0);
int T;cin >> T;
while (T--) solve();
return 0;
}
/*
1
2 5
.OO..
O..O.
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO
output:
3 1 0 0
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3796kb
input:
200 2 4 OOO. OO.. 2 3 OOO .O. 3 3 O.O OOO OO. 4 1 . . O O 1 2 .O 1 1 . 2 5 .OO.. .O.O. 2 1 O O 1 1 O 1 3 .OO 5 1 O O . O . 5 2 O. .. O. .O .. 5 3 ... ... .OO ..O OOO 3 5 ..O.O .O.O. .OO.O 5 2 .O OO O. O. .. 2 1 O O 3 5 .O.OO O...O ..OO. 1 5 ..... 5 1 O . O . . 5 3 OOO OO. .OO OO. O.O 2 1 O . 5 2 O. ...
output:
3 0 0 2 1 1 2 0 0 1 0 4 6 3 4 0 3 1 2 0 1 5 2 4 2 0 0 4 3 3 1 1 1 0 4 1 2 2 4 2 0 4 2 2 2 0 3 5 3 3 2 2 2 4 2 1 0 3 3 2 3 2 2 0 4 3 1 5 3 3 2 3 2 1 2 1 1 0 0 2 3 1 2 3 4 1 4 2 2 2 4 3 2 1 0 1 3 3 3 9 0 2 2 1 0 0 1 2 1 3 2 4 3 0 3 4 2 4 1 2 3 1 0 2 6 2 2 3 0 1 4 3 2 1 2 2 0 3 0 7 3 3 2 3 0 5 2 3 1 1 ...
result:
wrong answer 7th lines differ - expected: '3', found: '2'