QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#765410	#7733. Cool, It’s Yesterday Four Times More	Difficult_to_naming	WA	2ms	10108kb	C++14	3.9kb	2024-11-20 14:13:23	2024-11-20 14:13:24

Judging History

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

[2024-11-20 14:13:24]
评测

测评结果：WA
用时：2ms
内存：10108kb

查看

[2024-11-20 14:13:23]
提交

answer

#include <bits/stdc++.h>
#define int long long
const int fx[] = {1, -1, 0, 0}, fy[] = {0, 0, -1, 1};
int t, n, m, vis[1002][1003], ans, pd, can[1002][1002], sz;
char mp[1002][1002], s[1002][1002];
// O洞 .人 D空位
void dfs(int x, int y, int lst, int lstx, int lsty, char s[1002][1002]) {
    if (x < 1 || x > n || y < 1 || y > m || mp[x][y] == 'O' || vis[x][y])
        return;
    if (lst != -1) {
        // printf("%lld %lld %lld %lld\n", x, y, lstx, lsty);
        if (lst == 2 || lst == 1) {
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                    if (s[i][j] == '.') {
                        int dx = i + fx[lst], dy = j + fy[lst];
                        if (dx < 1 || dx > n || dy < 1 || dy > m ||
                            s[dx][dy] == 'O') {
                            int lx = x - lstx, ly = y - lsty;
                            int sx = dx - lx, sy = dy - ly;
                            // printf("AAA %lld %lld %lld %lld\n", i, j, lx,
                            // ly);
                            can[sx][sy] = 1;
                            s[i][j] = 'D';
                        } else
                            s[i][j] = 'D', s[dx][dy] = '.';
                    }
        } else {
            for (int i = n; i; i--)
                for (int j = m; j; j--)
                    if (s[i][j] == '.') {
                        int dx = i + fx[lst], dy = j + fy[lst];
                        if (dx < 1 || dx > n || dy < 1 || dy > m ||
                            s[dx][dy] == 'O') {
                            int lx = x - lstx, ly = y - lsty;
                            int sx = dx - lx, sy = dy - ly;
                            // printf("AAA %lld %lld %lld %lld\n", i, j, lx,
                            // ly);
                            can[sx][sy] = 1;
                            s[i][j] = 'D';
                        } else
                            s[i][j] = 'D', s[dx][dy] = '.';
                    }
        }
        // for (int I = 1; I <= n; puts(""), I++)
        //     for (int J = 1; J <= m; J++)
        //         printf("%c", s[I][J]);
        // puts("");
    }
    sz++, vis[x][y] = 1, dfs(x + 1, y, 0, lstx, lsty, s),
          dfs(x, y + 1, 3, lstx, lsty, s), dfs(x - 1, y, 1, lstx, lsty, s),
          dfs(x, y - 1, 2, lstx, lsty, s);
} // 0下 1上 2左 3右
signed main() {
    // freopen("kangaroo.in", "r", stdin);
    // freopen("kangaroo.out", "w", stdout);
    scanf("%lld", &t);
    for (; t--;) {
        scanf("%lld%lld", &n, &m), ans = 0;
        for (int i = 1; i <= n; i++)
            scanf("%s", mp[i] + 1);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                vis[i][j] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (mp[i][j] == 'O' || vis[i][j])
                    continue;
                sz = 0;
                for (int I = 1; I <= n; I++)
                    for (int J = 1; J <= m; J++)
                        s[I][J] = mp[I][J], can[I][J] = 0;
                // printf("%lld %lld :\n", i, j);
                dfs(i, j, -1, i, j, s);
                // for (int I = 1; I <= n; I++, puts(""))
                //     for (int J = 1; J <= m; J++)
                //         printf("%lld ", can[I][J]);
                for (int I = 1; I <= n; I++)
                    for (int J = 1; J <= m; J++)
                        if ((I != i || J != j) && !can[I][J] && mp[I][J] == '.')
                            goto NO;
                ans += sz;
            NO:;
            }
        printf("%lld\n", ans);
    }
    return 0;
}
// 枚举每个点能到达的点，若这个点可以胜利，那么这个点所在的联通块一定是可以胜利的、
// 胜利：对于一个点，能到的所有连通块使所有其他点过程中趋势

// 下发文件呢 /fn /fn /fn

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 5980kb

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: 2ms

memory: 10108kb

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 23rd lines differ - expected: '4', found: '0'