QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640888#7733. Cool, It’s Yesterday Four Times MoreDoubeecatWA 2ms3796kbC++203.7kb2024-10-14 16:42:212024-10-14 16:42:25

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 16:42:25]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3796kb
  • [2024-10-14 16:42:21]
  • 提交

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'