QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #101631 | #6377. LaLa and Magic Stone | willow# | WA | 8ms | 7424kb | C++14 | 2.7kb | 2023-04-30 15:43:36 | 2023-04-30 15:43:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2005, mod = 998244353;
const int step[4][7][2] = {{{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}, {2, 2}},
{{0, 0}, {2, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}, {2, 2}},
{{0, 0}, {0, 1}, {0, 2}, {2, 1}, {1, 2}, {2, 0}, {2, 2}},
{{0, 0}, {0, 1}, {0, 2}, {1, 0}, {2, 1}, {2, 0}, {2, 2}}};
int Add(int x, int y) {
return (x += y) >= mod ? x - mod : x;
}
int Mul(int x, int y) {
return 1ll * x * y % mod;
}
int n, m;
char s[maxn][maxn];
void Put(int x, int y, int k, char c) {
for(int i = 0; i < 7; ++ i) {
int nx = x + step[k][i][0], ny = y + step[k][i][1];
s[nx][ny] = c;
}
}
int Solve(int x, int y, int ans) {
// cerr << x << " " << y << " " << ans << " " << s[x][y] << endl;
// for(int i = 1; i <= n; ++ i, cerr << endl)
// for(int j = 1; j <= m; ++ j)
// cerr << s[i][j];
if(!ans)
return 0;
if(x == n + 1)
return ans;
if(s[x][y] == '1')
return Solve(x + (y == m), y == m ? 1 : y + 1, ans);
if(x >= n - 1 || y >= n - 1)
return 0;
int res = 0;
if(s[x + 1][y + 1] == '0') {
int f = 1;
for(int i = 0; i < 3 && f; ++ i)
for(int j = 0; j < 3 && f; ++ j)
if(s[x + i][y + j] == '1')
f = 0;
if(!f)
return 0;
if(y > 1 && x + 3 <= n && s[x + 1][y - 1] == '0' && s[x + 2][y - 1] == '0' && s[x + 3][y - 1] == '0' && s[x + 3][y] == '0' && s[x + 3][y + 1] == '0') {
Put(x, y, 2, '1');
Put(x + 1, y - 1, 3, '1');
res += Solve(x + (y == m), y == m ? 1 : y + 1, Add(ans, ans));
Put(x, y, 2, '1');
Put(x + 1, y - 1, 3, '1');
}
if(y + 3 <= m && x + 3 <= n && s[x + 1][y + 3] == '0' && s[x + 2][y + 3] == '0' && s[x + 3][y + 3] == '0' && s[x + 3][y + 2] == '0' && s[x + 3][y + 1] == '0') {
Put(x, y, 3, '1');
Put(x + 1, y + 1, 2, '1');
res += Solve(x + (y == m), y == m ? 1 : y + 1, Add(ans, ans));
Put(x, y, 3, '1');
Put(x + 1, y + 1, 2, '1');
}
return res;
}
else {
int k = -1;
if(s[x][y + 1] == '1') {
if(k == -1)
k = 1;
else
k = -2;
}
if(s[x + 2][y + 1] == '1') {
if(k == -1)
k = 0;
else
k = -2;
}
if(s[x + 1][y] == '1') {
if(k == -1)
k = 2;
else
k = -2;
}
if(s[x + 1][y + 2] == '1') {
if(k == -1)
k = 3;
else
k = -2;
}
if(k == -2)
return 0;
if(k != -1) {
Put(x, y, k, '1');
res += Solve(x + (y == m), y == m ? 1 : y + 1, ans);
Put(x, y, k, '0');
}
else {
for(k = 0; k < 4; ++ k) {
Put(x, y, k, '1');
res += Solve(x + (y == m), y == m ? 1 : y + 1, ans);
Put(x, y, k, '0');
}
}
return res;
}
return res;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i)
scanf("%s", s[i] + 1);
printf("%d\n", Solve(1, 1, 1));
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3616kb
input:
4 4 0001 0000 0000 1000
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
5 4 0001 0101 0000 1010 1000
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
3 3 111 111 111
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3492kb
input:
3 4 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
3 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 3ms
memory: 3556kb
input:
4 3 111 111 111 111
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
4 4 1111 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
4 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 2ms
memory: 5688kb
input:
1000 3 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 1...
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 4ms
memory: 7424kb
input:
1000 4 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 111...
output:
1
result:
ok 1 number(s): "1"
Test #11:
score: 0
Accepted
time: 4ms
memory: 6484kb
input:
1000 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
3 3 000 010 010
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 3ms
memory: 3604kb
input:
3 3 000 011 000
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
3 3 010 010 000
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
3 3 000 110 000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
4 4 1000 0000 0000 0001
output:
2
result:
ok 1 number(s): "2"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
4 4 0001 0000 0000 1000
output:
2
result:
ok 1 number(s): "2"
Test #18:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
3 3 010 101 101
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
3 4 1011 0100 1111
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
3 1000 10011010111111111111000101011100101000000011110011011000110000100110110110111110000111011001010010011100001111111011111111110010110100011101011100100100001110010011111011111101001110011010010110110011001100101010001101100111101001001001101000101011101000100100001111100000010010111101101001000...
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
4 3 010 101 110 000
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
4 4 0110 1010 1101 1110
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
4 1000 01001110100001111110010111111001110111001110100100101101001110110111001111101100111110001110100000010101110001100001011000100111001111101110100001010101100011101110000010110101101100001000111101111000110100110000110111111101111101000011100001001110011000110110001110110011010111101101101001000...
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 0ms
memory: 7316kb
input:
1000 3 011 011 101 011 101 011 100 101 110 010 101 010 010 100 100 000 010 101 011 110 101 110 011 101 100 110 011 011 101 101 111 001 101 100 110 110 101 011 010 100 100 110 110 100 110 101 111 011 101 001 101 101 001 110 110 010 101 110 010 100 010 110 010 110 111 101 100 001 000 001 110 001 111 0...
output:
0
result:
ok 1 number(s): "0"
Test #25:
score: 0
Accepted
time: 3ms
memory: 5512kb
input:
1000 4 1000 0000 1010 0100 0101 0011 1101 0000 1001 0001 1111 0100 1101 0111 1110 1001 0100 0011 0011 1000 1001 1100 0110 0100 1100 0111 0010 0110 1111 1101 1001 0010 1110 1100 1000 0111 0010 0100 1001 0101 1111 0000 0110 0011 0110 1000 0110 1111 0000 0000 1011 1000 0000 0101 1001 0001 0100 0110 011...
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: 0
Accepted
time: 8ms
memory: 6580kb
input:
1000 1000 00111010100111001111101110110011111101010111001010011001011000100100110011000111000000100010011101100011001001101110100001000101111100100110101010101011000111010101000110000110001100110011111000011100100001001110110000110010000111010110100001010100100101000011110001010111011011101111001011...
output:
0
result:
ok 1 number(s): "0"
Test #27:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
58 17 10001101010001111 10111101010000111 10001100010000000 00011000111000010 01110000111111010 00010000111111111 11110001111110001 11100010001100001 11100000000100001 11100000000100011 11110001000111000 00010001000110000 00000101000010000 00000101000010001 10001111100011111 11111111000111000 111000...
output:
0
result:
ok 1 number(s): "0"
Test #28:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
16 13 1111111111111 1111111111111 1000110001111 1000100000001 1000000000000 1100000010000 1111111111000 1111111111111 1110001111111 1110000111000 1110000110000 1111000110000 1100010000001 1000010000111 1000010000111 1000111000111
output:
0
result:
ok 1 number(s): "0"
Test #29:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
9 78 000111111111111111000111111111100011100010000001111111111111111111111111110001 010100011111111111000011111111100001000000000000111111110001111000110001110000 110100001111110001000011100011100001000000000000010111110000110000100001110000 1000000011111100001000111000011100010001000110000100001100...
output:
0
result:
ok 1 number(s): "0"
Test #30:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
18 55 1111110001111111111111000111111111111111111000111111111 1111110000100010001000000011100011000111110000111111111 1110000000111010000010000011100001000000010000111111111 1100001000100010000010100011100001000000000001100011111 1100001110001111000111111111110001100000001111100000101 11000111100001...
output:
0
result:
ok 1 number(s): "0"
Test #31:
score: 0
Accepted
time: 0ms
memory: 5780kb
input:
124 5 10001 10000 10000 11000 00011 00001 00001 10001 00011 00001 00001 10001 11111 00011 01011 01011 11111 11111 10001 00001 00001 00011 10001 00001 00001 00011 00011 01011 01011 11111 11111 11111 11000 10000 10000 10001 11111 11111 11111 11111 11000 10000 10000 10001 10001 10000 10000 11000 11000 ...
output:
1048576
result:
ok 1 number(s): "1048576"
Test #32:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
117 6 110001 111101 110001 111000 110000 110000 110001 111111 100011 100001 100001 110001 111111 111111 111111 111000 110000 110000 110001 100011 000011 000011 000111 000111 000011 000011 100011 000111 000011 000011 100011 111111 000101 010111 010000 110000 110000 110001 111111 111111 111111 111111 ...
output:
0
result:
ok 1 number(s): "0"
Test #33:
score: 0
Accepted
time: 2ms
memory: 5560kb
input:
25 19 1111111111111111111 0001111111111000111 1101111111111110111 0001110001111000111 1111100001111100011 1111100000001100001 1111100010101100001 1111111110101110001 0001111111111111000 1101100011111110000 0001000011000110000 1111000010000110001 1000000110000000111 0000111110001000011 00001111111110...
output:
8192
result:
ok 1 number(s): "8192"
Test #34:
score: 0
Accepted
time: 2ms
memory: 3900kb
input:
83 5 00011 00001 00001 10001 11111 10001 10000 10000 11000 00011 00001 00001 10001 00011 01111 00011 10001 00001 00001 00011 10001 10101 10101 11111 11111 10001 00001 00001 00011 10001 00001 00001 00011 11111 10001 00001 00001 00011 11111 10001 10000 10000 11000 00011 00001 00001 10001 11111 11111 1...
output:
32768
result:
ok 1 number(s): "32768"
Test #35:
score: 0
Accepted
time: 2ms
memory: 3856kb
input:
30 28 1111111111111111111110001111 1111000111111111000111101000 1110000000111110000110000000 1110000000010000000000110000 1110001000000000000000110001 1000111100000001110000000111 1010111111100011110001000011 1010111111111111111111000011 0001111111110001111111100011 0000110001100001000100011111 0000...
output:
33554432
result:
ok 1 number(s): "33554432"
Test #36:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
64 8 11111111 11111111 00011111 00001111 00001000 10000000 11110000 11110001 11111111 11100011 11000011 11000011 11000111 11111111 11000111 11000011 11000011 11100011 11111111 11100011 11000011 11000011 11000111 11111111 11100011 11100001 00000001 00000001 00001111 10001111 11100011 11000011 1100001...
output:
0
result:
ok 1 number(s): "0"
Test #37:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
5 141 111111000111111111000111111111111111111011111000111111111111111110100001111100011100010001110001100011100011110001100010001100010001111000111 100010000100011110000110001000111100001010001000000000011111110000100000000100001000010101100001100001100001100001100000000100000000110000111 1000000000...
output:
0
result:
ok 1 number(s): "0"
Test #38:
score: 0
Accepted
time: 3ms
memory: 3796kb
input:
10 73 1111111111111111100011111111111111111110001111111000011111111111101000011 1111100010001111000011111110001110001110000110001000011111000111101000001 1111000010111111000011111110000100001110000100001000000011000011100000001 111100001000111100011111000000010000111100010000100010000100000001111000...
output:
0
result:
ok 1 number(s): "0"
Test #39:
score: -100
Wrong Answer
time: 0ms
memory: 3604kb
input:
27 29 11000111111100011111111111111 11000011111000011100011111111 11000000011000011100001110001 11100001011000111100001110101 11111101011000111110001110101 11111111111000011111111110001 11100011111000011100011100001 11100001101000011100001100001 11100001101010001100001100011 111100011000000011100011...
output:
0
result:
wrong answer 1st numbers differ - expected: '67108864', found: '0'