QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372952 | #5270. Easily Distinguishable Triangles | kevinyang# | WA | 1ms | 3852kb | C++17 | 1.7kb | 2024-03-31 21:33:26 | 2024-03-31 21:33:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n;
bool good(int x, int y){
return x>=1 && x<=n && y>=1 && y<=n;
}
bool bad = false;
int solve(vector<vector<char>>arr){
vector<vector<bool>>vis(n+1,vector<bool>(n+1));
queue<pair<int,int>>q;
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++){
if(arr[i][j] == '#'){
vis[i][j] = true;
q.push({i,j});
}
}
for(int j = 2; j<n; j++){
if(arr[i][j] == '?' && arr[i][j-1]=='#' && arr[i][j+1] == '#'){
bad = true;
}
}
}
vector<int>dx = {0,0};
vector<int>dy = {-1,1};
while(q.size()){
auto cur = q.front(); q.pop();
int i = cur.first;
int j = cur.second;
for(int d = 0; d<2; d++){
int x = i+dx[d];
int y = j+dy[d];
if(good(x,y) && !vis[x][y] && arr[x][y]=='?'){
vis[x][y] = true;
q.push({x,y});
}
}
}
int ans = 1;
for(int i = 1; i<=n; i++){
int cur = 0;
for(int j = 1; j<=n; j++){
if(vis[i][j])continue;
if(arr[i][j] == '.' && cur){
ans*=(cur+1);
cur = 0;
ans%=mod;
}
if(arr[i][j]=='?'){
cur++;
}
}
//cout << cur << '\n';
if(cur){
ans*=cur+1;
ans%=mod;
}
}
return ans;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
vector<vector<char>>arr(n+1,vector<char>(n+1));
for(int i = 1; i<=n; i++){
string s;
cin >> s;
for(int j = 1; j<=n; j++){
arr[i][j] = s[j-1];
}
}
int a = solve(arr);
for(int i = 1; i<=n; i++){
for(int j = i; j<=n; j++){
swap(arr[i][j],arr[j][i]);
}
}
int b = solve(arr);
if(bad){
cout << "0\n";
return 0;
}
cout << (a*b)%mod << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3852kb
input:
2 .? ?#
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
3 #?? #?? ?##
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3 .#. #?# .#.
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
1 .
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
1 #
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
1 ?
output:
4
result:
ok 1 number(s): "4"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
2 ?. ?.
output:
12
result:
ok 1 number(s): "12"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
3 ?.? .#? ?.?
output:
256
result:
ok 1 number(s): "256"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
5 ????? .?.#. ???#? ?##?? ?.?.?
output:
12288
result:
ok 1 number(s): "12288"
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3772kb
input:
10 ...###???. ?.???.??#. ??.?????.. .#..?.???? ???...?..? .???.?..?? ??.????.?? .????.?.?? #.????.?#? ?.##???#??
output:
992902995
result:
wrong answer 1st numbers differ - expected: '0', found: '992902995'