QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#410590	#3162. Mini Battleship	frizzfrizz	AC ✓	1167ms	3748kb	C++14	2.2kb	2024-05-14 10:13:09	2024-05-14 10:13:10

Judging History

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

[2024-05-14 10:13:10]
评测

测评结果：AC
用时：1167ms
内存：3748kb

查看

[2024-05-14 10:13:09]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define A first
#define B first
#define SZ(x) int(x.size())

#define FR(i, a, b) for (int i = (a); i < (b); i++)
#define FOR(i, n) FR(i, 0, n)

int N, K, placed[6][6];
LL co = 0;
vector<int> szs;
char grid[6][6];
void gen(int boat)
{
    if (boat == K)
    {
        bool bad = false;
        FOR(i, N)
        {
            FOR(j, N)
            {
                if (grid[i][j] == 'X' && placed[i][j] == 1)
                    bad = true;
                if (grid[i][j] == 'O' && placed[i][j] == 0)
                    bad = true;
            }
        }
        if (!bad)
            co++;
    }
    FOR(i, N)
    {
        FOR(j, N)
        {
            if (j + szs[boat] - 1 < N)
            {
                FOR(k, szs[boat])
                {
                    if (grid[i][j + k] == 'X' || placed[i][j + k])
                        break;
                    if (k == szs[boat] - 1)
                    {
                        FOR(m, szs[boat])
                            placed[i][j + m] = 1;
                        gen(boat + 1);
                        FOR(m, szs[boat])
                            placed[i][j + m] = 0;
                    }
                }
            }
            if (szs[boat] == 1)
                continue;
            if (i + szs[boat] - 1 < N)
            {
                FOR(k, szs[boat])
                {
                    if (grid[i + k][j] == 'X' || placed[i + k][j])
                        break;
                    if (k == szs[boat] - 1)
                    {
                        FOR(m, szs[boat])
                            placed[i + m][j] = 1;
                        gen(boat + 1);
                        FOR(m, szs[boat])
                            placed[i + m][j] = 0;
                    }
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K;
    FOR(i, N)
        FOR(j, N)
            cin >> grid[i][j];
    FOR(i, K)
    {
        int a;
        cin >> a;
        szs.push_back(a);
    }
    gen(0);
    cout << co;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3636kb

input:

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

output:

result:

ok single line: '132'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3664kb

input:

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

output:

result:

ok single line: '6'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

2 2
..
..
2
2

output:

result:

ok single line: '4'

Test #4:

score: 0

Accepted

time: 3ms

memory: 3656kb

input:

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

output:

result:

ok single line: '80848'

Test #5:

score: 0

Accepted

time: 373ms

memory: 3664kb

input:

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

output:

result:

ok single line: '6375600'

Test #6:

score: 0

Accepted

time: 1167ms

memory: 3612kb

input:

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

output:

18840000

result:

ok single line: '18840000'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

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

output:

result:

ok single line: '1'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

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

output:

result:

ok single line: '1'

Test #9:

score: 0

Accepted

time: 15ms

memory: 3684kb

input:

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

output:

result:

ok single line: '1'

Test #10:

score: 0

Accepted

time: 15ms

memory: 3724kb

input:

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

output:

result:

ok single line: '0'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3660kb

input:

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

output:

result:

ok single line: '240'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3688kb

input:

1 1
.
1

output:

result:

ok single line: '1'

Test #13:

score: 0

Accepted

time: 0ms

memory: 3660kb

input:

1 1
O
1

output:

result:

ok single line: '1'

Test #14:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

1 1
X
1

output:

result:

ok single line: '0'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

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

output:

result:

ok single line: '0'

Test #16:

score: 0

Accepted

time: 5ms

memory: 3732kb

input:

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

output:

result:

ok single line: '192'

Test #17:

score: 0

Accepted

time: 2ms

memory: 3728kb

input:

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

output:

result:

ok single line: '0'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

2 2
O.
.X
2
1

output:

result:

ok single line: '2'

Test #19:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

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

output:

result:

ok single line: '432'

Test #20:

score: 0

Accepted

time: 59ms

memory: 3664kb

input:

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

output:

result:

ok single line: '0'

Test #21:

score: 0

Accepted

time: 0ms

memory: 3664kb

input:

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

output:

result:

ok single line: '8'

Test #22:

score: 0

Accepted

time: 34ms

memory: 3680kb

input:

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

output:

result:

ok single line: '6856'

Test #23:

score: 0

Accepted

time: 0ms

memory: 3748kb

input:

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

output:

result:

ok single line: '44'

Test #24:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

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

output:

result:

ok single line: '70'

Test #25:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

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

output:

result:

ok single line: '0'

Test #26:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

2 2
O.
..
1
2

output:

result:

ok single line: '6'

Test #27:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

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

output:

result:

ok single line: '714'

Test #28:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

2 2
..
OO
1
2

output:

result:

ok single line: '4'

Test #29:

score: 0

Accepted

time: 2ms

memory: 3684kb

input:

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

output:

result:

ok single line: '2390'

Test #30:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

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

output:

result:

ok single line: '36'

Test #31:

score: 0

Accepted

time: 4ms

memory: 3736kb

input:

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

output:

result:

ok single line: '48'

Test #32:

score: 0

Accepted

time: 1ms

memory: 3684kb

input:

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

output:

result:

ok single line: '3204'

Test #33:

score: 0

Accepted

time: 2ms

memory: 3628kb

input:

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

output:

result:

ok single line: '556'

Test #34:

score: 0

Accepted

time: 0ms

memory: 3664kb

input:

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

output:

result:

ok single line: '112'

Test #35:

score: 0

Accepted

time: 0ms

memory: 3656kb

input:

2 2
..
O.
1
1

output:

result:

ok single line: '6'

Test #36:

score: 0

Accepted

time: 1ms

memory: 3612kb

input:

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

output:

result:

ok single line: '2722'

Test #37:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

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

output:

result:

ok single line: '20'

Test #38:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

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

output:

result:

ok single line: '84'

Test #39:

score: 0

Accepted

time: 0ms

memory: 3732kb

input:

2 2
..
X.
1
2

output:

result:

ok single line: '2'

Test #40:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

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

output:

result:

ok single line: '63'

Test #41:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

2 2
.O
.X
2
2

output:

result:

ok single line: '0'

Test #42:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

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

output:

result:

ok single line: '44'

Test #43:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

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

output:

result:

ok single line: '0'

Test #44:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

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

output:

result:

ok single line: '8'

Test #45:

score: 0

Accepted

time: 0ms

memory: 3604kb

input:

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

output:

result:

ok single line: '334'