QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#189836#2880. Letters Q and FMaGnsi0#AC ✓3ms17684kbC++172.5kb2023-09-27 23:58:412023-09-27 23:58:42

Judging History

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

  • [2023-09-27 23:58:42]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:17684kb
  • [2023-09-27 23:58:41]
  • 提交

answer

/**
 *    author:  MaGnsi0
 *    created: 27.09.2023 18:36:24
**/
#include <bits/stdc++.h>

using namespace std;

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

const int dx_f[8] = {0, 1, 2, 3, 4, 0, 0, 2};
const int dy_f[8] = {0, 0, 0, 0, 0, 1, 2, 1};

const int dx_q[10] = {0, 0, 0, 1, 2, 3, 4, 1, 2, 2};
const int dy_q[10] = {0, 1, 2, 2, 2, 2, 2, 0, 0, 1};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    function<bool(int, int)> countQ = [&](int x, int y) {
        for (int i = 0; i < 10; ++i) {
            int nx = x + dx_q[i];
            int ny = y + dy_q[i];
            if (nx < 0 || nx >= n) { return false; }
            if (ny < 0 || ny >= m) { return false; }
            if (a[nx][ny] == '.') { return false; }
        }
        for (int i = 0; i < 10; ++i) {
            int nx = x + dx_q[i];
            int ny = y + dy_q[i];
            a[nx][ny] = '.';
        }
        return true;
    };
    function<bool(int, int)> countF = [&](int x, int y) {
        for (int i = 0; i < 8; ++i) {
            int nx = x + dx_f[i];
            int ny = y + dy_f[i];
            if (nx < 0 || nx >= n) { return false; }
            if (ny < 0 || ny >= m) { return false; }
            if (a[nx][ny] == '.') { return false; }
        }
        for (int i = 0; i < 8; ++i) {
            int nx = x + dx_f[i];
            int ny = y + dy_f[i];
            a[nx][ny] = '.';
        }
        return true;
    };
    function<void(int, int, int, int)> solve = [&](int Q, int F, int i, int j) {
        int nj = (j + 1 < m ? j + 1 : 0);
        int ni = (j + 1 < m ? i : i + 1);
        if (ni == n) {
            cout << Q << " " << F;
            exit(0);
        }
        if (a[i][j] == '.') {
            solve(Q, F, ni, nj);
            return;
        }
        if (countF(i, j)) {
            solve(Q, F + 1, ni, nj);
            for (int k = 0; k < 8; ++k) {
                int nx = i + dx_f[k];
                int ny = j + dy_f[k];
                a[nx][ny] = '#';
            }
        }
        if (countQ(i, j)) {
            solve(Q + 1, F, ni, nj);
            for (int k = 0; k < 10; ++k) {
                int nx = i + dx_q[k];
                int ny = j + dy_q[k];
                a[nx][ny] = '#';
            }
        }
    };
    solve(0, 0, 0, 0);
}

详细

Test #1:

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

input:

5 3
###
#.#
###
..#
..#

output:

1 0

result:

ok single line: '1 0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

5 3
###
#..
##.
#..
#..

output:

0 1

result:

ok single line: '0 1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

5 8
###..###
#.#..#..
###..##.
..#..#..
..#..#..

output:

1 1

result:

ok single line: '1 1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3452kb

input:

8 8
.....###
###..#.#
#.######
###.####
#.###.##
#.#.###.
..#...#.
......#.

output:

2 2

result:

ok single line: '2 2'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

10 10
....###...
....#.###.
....###...
....#.##..
###.#.####
#.###.##..
###.#..##.
#.###..#..
#...#..#..
....#.....

output:

1 4

result:

ok single line: '1 4'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

50 50
###..................###.......###...###.......###
#.....###.........####..###....#.....#.####.####.#
#####.#...######..#.###.#.###..##....####...#..###
#.#...##..#.##....####..###....#.......###..##...#
#.##..#...#####.###.##..#.##...#.###...##...#....#
..#####.###.##..#.#.#...#.#......#.####...

output:

66 70

result:

ok single line: '66 70'

Test #7:

score: 0
Accepted
time: 1ms
memory: 5048kb

input:

100 100
....###..###........######..###..###..........###....................................###...###......
.####....#.#..#######.##.####.#..#.#....###...#....###........###...###..###..###.####.....#.####...
.#..##...###..#.##..######.####..###.####.....######..........#..####....#.####...#..##.##...

output:

280 298

result:

ok single line: '280 298'

Test #8:

score: 0
Accepted
time: 0ms
memory: 17644kb

input:

300 300
...............###.###....###..###....######........###...###..###..###....###..........###..######......###....#########...............###.............###.###..###.###.........###.........###..........###....###.######.......###......###.....###...................###..###.......###............

output:

2472 2694

result:

ok single line: '2472 2694'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

5 298
.############.######..#########.######.###.######.######.######.##################.############.###..###..###..###.###.#####################.###..#########..###..###.###.######..###..###..###.######.###..###..######..###.###.###.######.###.###..######..#########.#########.######.###..###.#####...

output:

41 39

result:

ok single line: '41 39'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

299 3
###
#..
##.
#..
#..
...
...
###
#.#
###
..#
..#
...
...
...
###
#.#
###
..#
..#
...
###
#.#
###
..#
..#
###
#.#
###
..#
..#
...
###
#..
##.
#..
#..
...
...
...
###
#..
##.
#..
#..
###
#.#
###
..#
..#
...
...
###
#..
##.
#..
#..
...
...
###
#.#
###
..#
..#
###
#.#
###
..#
..#
###
#..
##.
#..
#....

output:

26 20

result:

ok single line: '26 20'

Test #11:

score: 0
Accepted
time: 3ms
memory: 8092kb

input:

123 234
.........###....###.###....###....###....###....###.....###.......######...........###..............###.###....###.......###...###......###........###............................###........###.......###....###...###..###..###.........
###..###.#...####.#.#.#....#.#.####.####.#.#....#..###..#...

output:

785 838

result:

ok single line: '785 838'

Test #12:

score: 0
Accepted
time: 2ms
memory: 8024kb

input:

234 123
.###........###.###...........###..######.............###....###...######..######................................###.......
.#.#........#.#.#.#.###..###..#....#..#.#.............#.####.#.#...#..#.#..#..#.........###..............###.###.#.#######.
.###........###.###.#.####.#####...##.###......

output:

805 836

result:

ok single line: '805 836'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

5 3
...
...
...
...
...

output:

0 0

result:

ok single line: '0 0'

Test #14:

score: 0
Accepted
time: 3ms
memory: 17612kb

input:

300 300
.......................................................................................................................................................................................................................................................................................................

output:

0 0

result:

ok single line: '0 0'

Test #15:

score: 0
Accepted
time: 0ms
memory: 17684kb

input:

300 300
###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###......

output:

8019 0

result:

ok single line: '8019 0'

Test #16:

score: 0
Accepted
time: 0ms
memory: 17636kb

input:

300 300
###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###........###......

output:

0 8019

result:

ok single line: '0 8019'