QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#645263 | #7733. Cool, It’s Yesterday Four Times More | hamster | WA | 1ms | 3612kb | C++23 | 2.0kb | 2024-10-16 17:27:09 | 2024-10-16 17:27:14 |
Judging History
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'