QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372952#5270. Easily Distinguishable Triangleskevinyang#WA 1ms3852kbC++171.7kb2024-03-31 21:33:262024-03-31 21:33:28

Judging History

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

  • [2024-03-31 21:33:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3852kb
  • [2024-03-31 21:33:26]
  • 提交

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'