QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#873771#3162. Mini BattleshipLaStataleBlue#AC ✓632ms3712kbC++171.1kb2025-01-26 22:33:272025-01-26 22:33:28

Judging History

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

  • [2025-01-26 22:33:28]
  • 评测
  • 测评结果：AC
  • 用时：632ms
  • 内存：3712kb
查看
  • [2025-01-26 22:33:27]
  • 提交

answer

#include <bits/stdc++.h>

#define int int64_t
using namespace std;

string m[5];
int l[5];
bool occ[5][5];
int n,k;

int fata(int li) {
	if(li==k) {
		for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if(m[i][j]=='O' && occ[i][j]==0) return 0;
		return 1;
	}
	int ans=0;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<n; ++j) {
			if(i+l[li]<=n) {
				bool can=1;
				for(int ni=i; ni<i+l[li]; ++ni) if(occ[ni][j]) can=0;
				if(can) {
					for(int ni=i; ni<i+l[li]; ++ni) occ[ni][j]=1;
					ans+=fata(li+1);
					for(int ni=i; ni<i+l[li]; ++ni) occ[ni][j]=0;
				}
			}
			if(l[li]>1 && j+l[li]<=n) {
				bool can=1;
				for(int nj=j; nj<j+l[li]; ++nj) if(occ[i][nj]) can=0;
				if(can) {
					for(int nj=j; nj<j+l[li]; ++nj) occ[i][nj]=1;
					ans+=fata(li+1);
					for(int nj=j; nj<j+l[li]; ++nj) occ[i][nj]=0;
				}
			}
		}
	}
	return ans;
}

signed main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin>>n>>k;
	for(int i=0; i<n; ++i) {
		cin>>m[i];
	}
	for(int i=0; i<k; ++i) cin>>l[i];
	for(int i=0; i<n; ++i) {
		for(int j=0; j<n; ++j) {
			if(m[i][j]=='X') occ[i][j]=1;
		}
	}
	cout<<fata(0)<<endl;

	return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

132

result:

ok single line: '132'

Test #2:

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

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: 3584kb

input:

2 2
..
..
2
2

output:

4

result:

ok single line: '4'

Test #4:

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

input:

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

output:

80848

result:

ok single line: '80848'

Test #5:

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

input:

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

output:

6375600

result:

ok single line: '6375600'

Test #6:

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

input:

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

output:

18840000

result:

ok single line: '18840000'

Test #7:

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

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: 0ms
memory: 3712kb

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: 3584kb

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: 3584kb

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: 3584kb

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: 0ms
memory: 3584kb

input:

1 1
.
1

output:

1

result:

ok single line: '1'

Test #13:

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

input:

1 1
O
1

output:

1

result:

ok single line: '1'

Test #14:

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

input:

1 1
X
1

output:

0

result:

ok single line: '0'

Test #15:

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

input:

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

output:

0

result:

ok single line: '0'

Test #16:

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

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: 0ms
memory: 3584kb

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: 0ms
memory: 3584kb

input:

2 2
O.
.X
2
1

output:

2

result:

ok single line: '2'

Test #19:

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

input:

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

output:

432

result:

ok single line: '432'

Test #20:

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

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: 0ms
memory: 3584kb

input:

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

output:

8

result:

ok single line: '8'

Test #22:

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

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: 0ms
memory: 3584kb

input:

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

output:

44

result:

ok single line: '44'

Test #24:

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

input:

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

output:

70

result:

ok single line: '70'

Test #25:

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

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: 3712kb

input:

2 2
O.
..
1
2

output:

6

result:

ok single line: '6'

Test #27:

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

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: 0ms
memory: 3584kb

input:

2 2
..
OO
1
2

output:

4

result:

ok single line: '4'

Test #29:

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

input:

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

output:

2390

result:

ok single line: '2390'

Test #30:

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

input:

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

output:

36

result:

ok single line: '36'

Test #31:

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

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: 3584kb

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: 3584kb

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: 3584kb

input:

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

output:

112

result:

ok single line: '112'

Test #35:

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

input:

2 2
..
O.
1
1

output:

6

result:

ok single line: '6'

Test #36:

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

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: 0ms
memory: 3584kb

input:

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

output:

20

result:

ok single line: '20'

Test #38:

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

input:

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

output:

84

result:

ok single line: '84'

Test #39:

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

input:

2 2
..
X.
1
2

output:

2

result:

ok single line: '2'

Test #40:

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

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: 3584kb

input:

2 2
.O
.X
2
2

output:

0

result:

ok single line: '0'

Test #42:

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

input:

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

output:

44

result:

ok single line: '44'

Test #43:

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

input:

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

output:

0

result:

ok single line: '0'

Test #44:

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

input:

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

output:

8

result:

ok single line: '8'

Test #45:

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

input:

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

output:

334

result:

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

Server Time: 2025-02-03 19:06:32 | OpenSource Project