QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#739215	#7733. Cool, It’s Yesterday Four Times More	dddfff	WA	71ms	7736kb	C++23	3.3kb	2024-11-12 21:10:49	2024-11-12 21:10:50

Judging History

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

[2024-11-12 21:10:50]
评测

测评结果：WA
用时：71ms
内存：7736kb

查看

[2024-11-12 21:10:49]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
typedef pair<int, int> PII;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int T;
int n, m, cnt;
int a[N][N];
bool vis[N][N], notlive[N][N];
vector<PII> g[N * N];
char x;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void BFS(int x, int y, int cnt)
{
    vis[x][y] = 1;
    g[cnt].push_back({x, y});
    queue<PII> q;
    q.push({x, y});
    while (q.size())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 1 || tx > n || ty < 1 || ty > m)
            {
                continue;
            }
            if (a[tx][ty] && !vis[tx][ty])
            {
                g[cnt].push_back({tx, ty});
                vis[tx][ty] = 1;
                q.push({tx, ty});
            }
        }
    }
}
void solve()
{
    // code
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> x;
            if (x == '.')
            {
                a[i][j] = 1;
            }
            else
            {
                a[i][j] = 0;
            }
            vis[i][j] = 0;
            g[(i - 1) * m + j].clear();
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (!vis[i][j] && a[i][j])
            {
                cnt++;
                BFS(i, j, cnt);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= cnt; i++)
    {
        int nx = g[i][0].first, ny = g[i][0].second;
        for (int j = 1; j < g[i].size(); j++)
        {
            int tx = g[i][j].first - nx;
            int ty = g[i][j].second - ny;
            for (int k = 1; k <= cnt; k++)
            {
                if (i == k)
                    continue;
                for (auto i : g[k])
                {
                    int nex = i.first;
                    int ney = i.second;
                    int nnex = nex + tx;
                    int nney = ney + ty;
                    if (!notlive[nex][ney])
                    {
                        if (nnex < 1 || nnex > n || nney < 1 || nney > m || a[nnex][nney] == 0)
                        {
                            notlive[nex][ney] = 1;
                        }
                    }
                }
            }
        }
        bool flag = 1;
        for (int k = 1; k <= cnt; k++)
        {
            if (i == k)
                continue;
            for (auto i : g[k])
            {
                int nex = i.first;
                int ney = i.second;
                if (!notlive[nex][ney])
                {
                    flag = 0;
                }
            }
            for (auto i : g[k])
            {
                notlive[i.first][i.second] = 0;
            }
        }
        if (flag)
            ans += g[i].size();
    }
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 5912kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

result:

ok 4 lines

Test #2:

score: -100

Wrong Answer

time: 71ms

memory: 7736kb

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:

result:

wrong answer 5th lines differ - expected: '1', found: '2'