QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645263#7733. Cool, It’s Yesterday Four Times MorehamsterWA 1ms3612kbC++232.0kb2024-10-16 17:27:092024-10-16 17:27:14

Judging History

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

  • [2024-10-16 17:27:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3612kb
  • [2024-10-16 17:27:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using pi = pair<int, int>;
template<class... Args> void _(Args... args) {
	auto print = [&](auto x) { cout << x << " "; };
	cout << "--->";
	int arr[] = {(print(args), 0)...};
	cout << "\n";
}
struct KUAI
{
	int lon=0,hei=0,siz=0;
};

void Solve(){
	int n,m;cin>>n>>m;
	string s[n];vector<vector<int>> vis(n,vector<int>(m,0));int cnt=0;
	for(int i=0;i<n;i++)cin>>s[i];
	vector<KUAI> kuai{{-1,-1,-1}};
	auto ok=[&](int x,int y)
	{
		return ((x<n && y<m) && s[x][y]=='.');
	};
	auto bfs=[&](int x,int y)
	{
		cnt++;
		kuai.push_back({0,0,0,});
		queue<pi> pq;pq.push({x,y});
		vis[x][y]=cnt;
		int x1=LLONG_MAX,x2=-1,y1=LLONG_MAX,y2=-1;
		while(!pq.empty())
		{
			auto [xx,yy] = pq.front();pq.pop();
			//_(xx,yy);
			kuai[cnt].siz++;
			x1=min(x1,xx);x2=max(x2,xx);
			y1=min(y1,yy);y2=max(y2,yy);
			kuai[cnt].lon=max(kuai[cnt].lon,y2-y1+1);
			kuai[cnt].hei=max(kuai[cnt].hei,x2-x1+1);
			if(ok(xx+1,yy)&&vis[xx+1][yy]==0) pq.push({xx+1,yy}),vis[xx+1][yy]=cnt;
			if(ok(xx-1,yy)&&vis[xx-1][yy]==0) pq.push({xx-1,yy}),vis[xx-1][yy]=cnt;
			if(ok(xx,yy+1)&&vis[xx][yy+1]==0) pq.push({xx,yy+1}),vis[xx][yy+1]=cnt;
			if(ok(xx,yy-1)&&vis[xx][yy-1]==0) pq.push({xx,yy-1}),vis[xx][yy-1]=cnt;
		}
	};
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(vis[i][j]==0&&s[i][j]=='.')bfs(i,j);
	int ans=0;
	for(int i=1;i<=kuai.size()-1;i++)
	{
		bool is=1;
		for(int j=1;j<=kuai.size()-1;j++)
		{
			if(i==j)continue;
			if(!(kuai[i].siz>kuai[j].siz || kuai[i].hei>kuai[j].hei || kuai[i].lon>kuai[j].lon))
			{
				is=0;
			}
		}
		if(is)ans+=kuai[i].siz;
	}
	cout<<ans<<endl;
}
signed main() {
#ifdef _LOCAL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int Task = 1;
	cin >> Task;
	while (Task--) Solve();
}

int __OI_INIT__ = []() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed << setprecision(12);
	return 0;
}();

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

3
1
0
0

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3612kb

input:

200
2 4
OOO.
OO..
2 3
OOO
.O.
3 3
O.O
OOO
OO.
4 1
.
.
O
O
1 2
.O
1 1
.
2 5
.OO..
.O.O.
2 1
O
O
1 1
O
1 3
.OO
5 1
O
O
.
O
.
5 2
O.
..
O.
.O
..
5 3
...
...
.OO
..O
OOO
3 5
..O.O
.O.O.
.OO.O
5 2
.O
OO
O.
O.
..
2 1
O
O
3 5
.O.OO
O...O
..OO.
1 5
.....
5 1
O
.
O
.
.
5 3
OOO
OO.
.OO
OO.
O.O
2 1
O
.
5 2
O.
...

output:

3
0
0
2
1
1
3
0
0
1
0
4
9
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
4
5
2
3
7
3
0
6
2
2
2
0
4
6
6
3
3
2
3
5
2
1
0
3
3
4
4
2
2
0
7
6
4
8
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
6
1
6
2
2
3
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
6
2
5
1
3
3
4
0
2
11
2
2
4
0
4
4
6
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
1...

result:

wrong answer 12th lines differ - expected: '7', found: '4'