QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #101632 | #6377. LaLa and Magic Stone | willow# | WA | 8ms | 7016kb | C++14 | 2.9kb | 2023-04-30 15:48:21 | 2023-04-30 15:48:25 |
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 >= m - 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; // , cerr << x + i << " " << y + j << endl;
if(!f)
return 0;
// cerr << s[x + 1][y - 1] << " " << s[x + 2][y - 1] << " " << s[x + 3][y - 1] << " " << s[x + 3][y] << " " << s[x + 3][y + 1] << endl;
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: 3784kb
input:
4 4 0001 0000 0000 1000
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
5 4 0001 0101 0000 1010 1000
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3804kb
input:
3 3 111 111 111
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
3 4 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
4 3 111 111 111 111
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4 4 1111 1111 1111 1111
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 2ms
memory: 3800kb
input:
4 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 3ms
memory: 6904kb
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: 3ms
memory: 6748kb
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: 5ms
memory: 5512kb
input:
1000 1000 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
3 3 000 010 010
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
3 3 000 011 000
output:
1
result:
ok 1 number(s): "1"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
3 3 010 010 000
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
3 3 000 110 000
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 4 1000 0000 0000 0001
output:
2
result:
ok 1 number(s): "2"
Test #17:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
4 4 0001 0000 0000 1000
output:
2
result:
ok 1 number(s): "2"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
3 3 010 101 101
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
3 4 1011 0100 1111
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
3 1000 10011010111111111111000101011100101000000011110011011000110000100110110110111110000111011001010010011100001111111011111111110010110100011101011100100100001110010011111011111101001110011010010110110011001100101010001101100111101001001001101000101011101000100100001111100000010010111101101001000...
output:
0
result:
ok 1 number(s): "0"
Test #21:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
4 3 010 101 110 000
output:
0
result:
ok 1 number(s): "0"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
4 4 0110 1010 1101 1110
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
4 1000 01001110100001111110010111111001110111001110100100101101001110110111001111101100111110001110100000010101110001100001011000100111001111101110100001010101100011101110000010110101101100001000111101111000110100110000110111111101111101000011100001001110011000110110001110110011010111101101101001000...
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 3ms
memory: 6356kb
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: 7016kb
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: 6960kb
input:
1000 1000 00111010100111001111101110110011111101010111001010011001011000100100110011000111000000100010011101100011001001101110100001000101111100100110101010101011000111010101000110000110001100110011111000011100100001001110110000110010000111010110100001010100100101000011110001010111011011101111001011...
output:
0
result:
ok 1 number(s): "0"
Test #27:
score: 0
Accepted
time: 0ms
memory: 3852kb
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: 0ms
memory: 3668kb
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: -100
Wrong Answer
time: 0ms
memory: 3616kb
input:
9 78 000111111111111111000111111111100011100010000001111111111111111111111111110001 010100011111111111000011111111100001000000000000111111110001111000110001110000 110100001111110001000011100011100001000000000000010111110000110000100001110000 1000000011111100001000111000011100010001000110000100001100...
output:
8388608
result:
wrong answer 1st numbers differ - expected: '0', found: '8388608'