QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#139996#3162. Mini BattleshipKirill22#AC ✓179ms3636kbC++171.9kb2023-08-14 22:20:172023-08-14 22:20:18

Judging History

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

  • [2023-08-14 22:20:18]
  • 评测
  • 测评结果：AC
  • 用时：179ms
  • 内存：3636kb
查看
  • [2023-08-14 22:20:17]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

const int N = 5;
int n, k, s[N], ans = 0, usd[N][N];
string a[N];
vector<pair<int, int>> need;

void solve(int c) {
    if (c == k) {
        for (auto [x, y] : need) {
            if (!usd[x][y]) {
                return;
            }
        }
        ans++;
        return;
    }
    int l = s[c];
    for (int i = 0; i + l - 1 < n; i++) {
        for (int j = 0; j < n; j++) {
            bool f = true;
            for (int p = i; p < i + l; p++) {
                f &= !usd[p][j];
            }
            if (f) {
                for (int p = i; p < i + l; p++) {
                    usd[p][j] = 1;
                }
                solve(c + 1);
                for (int p = i; p < i + l; p++) {
                    usd[p][j] = 0;
                }
            }
        }
    }
    if (l > 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j + l - 1 < n; j++) {
                bool f = true;
                for (int p = j; p < j + l; p++) {
                    f &= !usd[i][p];
                }
                if (f) {
                    for (int p = j; p < j + l; p++) {
                        usd[i][p] = 1;
                    }
                    solve(c + 1);
                    for (int p = j; p < j + l; p++) {
                        usd[i][p] = 0;
                    }
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 'O') {
                need.push_back({i, j});
            }
            if (a[i][j] == 'X') {
                usd[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < k; i++) {
        cin >> s[i];
    }
    solve(0);
    cout << ans;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3
....
.OX.
....
O..X
3
2
1

output:

132

result:

ok single line: '132'

Test #2:

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

input:

4 4
.X.X
.XX.
...X
....
1
2
3
4

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2 2
..
..
2
2

output:

4

result:

ok single line: '4'

Test #4:

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

input:

5 5
.....
.....
.....
.....
.....
5
4
3
3
2

output:

80848

result:

ok single line: '80848'

Test #5:

score: 0
Accepted
time: 26ms
memory: 3420kb

input:

5 5
.....
.....
.....
.....
.....
1
1
1
1
1

output:

6375600

result:

ok single line: '6375600'

Test #6:

score: 0
Accepted
time: 179ms
memory: 3420kb

input:

5 5
.....
.....
.....
.....
.....
2
2
2
2
2

output:

18840000

result:

ok single line: '18840000'

Test #7:

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

input:

5 5
.....
XX...
..XXX
XXXX.
....X
5
1
4
2
3

output:

1

result:

ok single line: '1'

Test #8:

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

input:

5 5
OOOOO
XXOOO
OOXXX
XXXXO
OOOOX
5
1
4
2
3

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 5ms
memory: 3428kb

input:

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

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 5ms
memory: 3428kb

input:

5 5
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
5
1
4
2
3

output:

0

result:

ok single line: '0'

Test #11:

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

input:

5 5
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
5
5
5
5
5

output:

240

result:

ok single line: '240'

Test #12:

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

input:

1 1
.
1

output:

1

result:

ok single line: '1'

Test #13:

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

input:

1 1
O
1

output:

1

result:

ok single line: '1'

Test #14:

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

input:

1 1
X
1

output:

0

result:

ok single line: '0'

Test #15:

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

input:

4 5
....
....
....
....
4
4
4
4
4

output:

0

result:

ok single line: '0'

Test #16:

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

input:

5 5
OX.XO
XX.XX
.....
XX.XX
OX.XO
1
1
2
1
1

output:

192

result:

ok single line: '192'

Test #17:

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

input:

5 5
OX.XO
XX.XX
.....
XX.XX
OX.XO
1
1
2
2
1

output:

0

result:

ok single line: '0'

Test #18:

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

input:

2 2
O.
.X
2
1

output:

2

result:

ok single line: '2'

Test #19:

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

input:

3 5
...
...
...
2
2
1
2
2

output:

432

result:

ok single line: '432'

Test #20:

score: 0
Accepted
time: 10ms
memory: 3412kb

input:

5 4
O...O
.....
..O..
.....
O...O
2
2
2
2

output:

0

result:

ok single line: '0'

Test #21:

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

input:

3 2
O.O
.X.
...
3
2

output:

8

result:

ok single line: '8'

Test #22:

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

input:

5 5
X...O
.....
O...X
O.X..
.....
1
1
2
2
5

output:

6856

result:

ok single line: '6856'

Test #23:

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

input:

3 3
.O.
...
OO.
3
2
2

output:

44

result:

ok single line: '44'

Test #24:

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

input:

4 3
....
..X.
....
O..X
4
3
1

output:

70

result:

ok single line: '70'

Test #25:

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

input:

3 3
O.X
.X.
XO.
1
3
3

output:

0

result:

ok single line: '0'

Test #26:

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

input:

2 2
O.
..
1
2

output:

6

result:

ok single line: '6'

Test #27:

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

input:

4 4
.X..
..XX
.O..
X..O
1
3
1
1

output:

714

result:

ok single line: '714'

Test #28:

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

input:

2 2
..
OO
1
2

output:

4

result:

ok single line: '4'

Test #29:

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

input:

4 4
....
O...
....
.OO.
3
1
1
2

output:

2390

result:

ok single line: '2390'

Test #30:

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

input:

3 3
...
.X.
.XO
2
1
2

output:

36

result:

ok single line: '36'

Test #31:

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

input:

5 5
O.X.O
O...O
XO...
.X.X.
.O...
1
3
1
3
5

output:

48

result:

ok single line: '48'

Test #32:

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

input:

5 5
OO.X.
....X
X....
.....
.....
2
2
5
4
2

output:

3204

result:

ok single line: '3204'

Test #33:

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

input:

5 5
..OX.
..X..
.....
O....
OXX..
5
1
1
2
5

output:

556

result:

ok single line: '556'

Test #34:

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

input:

5 2
.....
..X..
.X...
...O.
.....
2
4

output:

112

result:

ok single line: '112'

Test #35:

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

input:

2 2
..
O.
1
1

output:

6

result:

ok single line: '6'

Test #36:

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

input:

5 4
.X.X.
X..O.
...O.
.....
X..X.
1
3
4
2

output:

2722

result:

ok single line: '2722'

Test #37:

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

input:

3 3
O..
XO.
.O.
1
1
2

output:

20

result:

ok single line: '20'

Test #38:

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

input:

4 3
...O
..O.
....
....
1
1
1

output:

84

result:

ok single line: '84'

Test #39:

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

input:

2 2
..
X.
1
2

output:

2

result:

ok single line: '2'

Test #40:

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

input:

4 3
X..O
....
O...
.X..
1
4
2

output:

63

result:

ok single line: '63'

Test #41:

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

input:

2 2
.O
.X
2
2

output:

0

result:

ok single line: '0'

Test #42:

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

input:

4 2
...O
....
....
....
4
2

output:

44

result:

ok single line: '44'

Test #43:

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

input:

4 2
XO..
....
X...
.X..
4
4

output:

0

result:

ok single line: '0'

Test #44:

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

input:

4 4
..O.
....
..X.
.XOO
4
4
1
1

output:

8

result:

ok single line: '8'

Test #45:

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

input:

4 2
....
....
....
..X.
2
2

output:

334

result:

ok single line: '334'
English 繁體中文 简体中文

Server Time: 2025-01-21 01:50:28 | OpenSource Project