QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#630130#7733. Cool, It’s Yesterday Four Times MoreyouthpaulWA 2ms3700kbC++202.4kb2024-10-11 16:40:022024-10-11 16:40:03

Judging History

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

  • [2024-10-11 16:40:03]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3700kb
  • [2024-10-11 16:40:02]
  • 提交

answer

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

const int N = 1005;

std::vector<std::pair<int, int>> mv = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while(t--){
        int n, m;
        std::cin >> n >> m;
        std::vector<std::string> mp(n + 1);
        std::vector<std::vector<std::vector<std::vector<bool>>>> vis(n + 1, 
            std::vector<std::vector<std::vector<bool>>>(m + 1, 
             std::vector<std::vector<bool>>(n + 1, std::vector<bool>(m + 1, false))));
        auto f = vis;
        fore(i, 1, n + 1){
            std::cin >> mp[i];
            mp[i] = '0' + mp[i];
        }

        auto in = [&](int x, int y) -> bool {
            return x > 0 && x <= n && y > 0 && y <= m;
        };

        auto dfs = [&](auto self, int x, int y, int s, int e) -> bool {
            if(!in(s, e)) return true;
            if(vis[x][y][s][e]) return f[x][y][s][e];
            vis[x][y][s][e] = true;
            if(mp[s][e] != '.') return f[x][y][s][e] = true;

            for(auto [dx, dy] : mv){
                int xx = x + dx, yy = y + dy;
                int ss = s + dx, ee = e + dy;
                if(in(xx, yy) && mp[xx][yy] == '.'){
                    if(self(self, xx, yy, ss, ee)) return f[x][y][s][e] = true;
                }
            }

            return false;
        };


        fore(x, 1, n + 1)
            fore(y, 1, m + 1)
                fore(s, 1, n + 1)
                    fore(e, 1, m + 1)
                        if(!vis[x][y][s][e])
                            dfs(dfs, x, y, s, e);
        
        int ans = 0;
        fore(x, 1, n + 1)
            fore(y, 1, m + 1){
                if(mp[x][y] != '.') continue;
                int cnt = 0;
                fore(s, 1, n + 1)
                    fore(e, 1, m + 1)
                        cnt += f[x][y][s][e];
                ans += (cnt == n * m - 1);
            }

        std::cout << ans << endl;
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3660kb

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: 3700kb

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
3
0
0
1
0
6
8
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
6
5
2
3
7
3
0
6
2
2
2
0
4
6
4
3
2
2
2
5
2
1
0
3
3
3
4
2
2
0
7
5
4
8
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
6
1
6
2
2
3
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
6
2
5
1
3
3
4
0
2
11
2
2
4
0
4
4
5
2
1
2
3
0
5
0
16
4
3
2
5
0
8
3
3
1...

result:

wrong answer 12th lines differ - expected: '7', found: '6'