ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#195686 | #3419. 方格判定 | cyqiu | 100 | 282ms | 6164kb | C++11 | 2.1kb | 2023-10-18 20:34:55 | 2023-10-18 22:31:44 |
answer
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int G[1001][1001];
bool vis[1001][1001];
int n,m;
struct bfs_node{
int x,y;
};
constexpr int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int homo_filled(int i,int j,int fromcol,int col){
queue<bfs_node> q;
q.push(bfs_node({i,j}));
G[i][j]=2;
int cnt=1;
vis[i][j]=1;
while(q.size()){
bfs_node fnt=q.front();
q.pop();
for(int k=0;k<4;k++){
bfs_node tmp({fnt.x+dx[k],fnt.y+dy[k]});
if(tmp.x>=1 && tmp.x<=n && tmp.y>=1 && tmp.y<=m && G[tmp.x][tmp.y]==fromcol){
q.push(tmp);
G[tmp.x][tmp.y]=col;
++cnt;
vis[tmp.x][tmp.y]=1;
}
}
}
return cnt;
}
int cntc,cnts;
constexpr int Cblkcnt=147,Sblkcnt=112;
void thist(int i,int j){
int cnt1=0,cnt2=0;
queue<bfs_node> q;
q.push({i,j});
cnt1++;
while(q.size()){
bfs_node fnt=q.front();
q.pop();
for(int k=0;k<4;k++){
bfs_node tmp({fnt.x+dx[k],fnt.y+dy[k]});
if(tmp.x>=1 && tmp.x<=n && tmp.y>=1 && tmp.y<=m && G[tmp.x][tmp.y] && !vis[tmp.x][tmp.y]){
q.push(tmp);
if(G[tmp.x][tmp.y]==1) ++cnt1;
else if(G[tmp.x][tmp.y]==2) ++cnt2;
vis[tmp.x][tmp.y]=1;
}
}
}
cnt2/=12;
//146x+112y=cnt1
//2x+y=cnt2
//y=cnt2-2x
//147x+112(cnt2-2x)=cnt1
//147x+112*cnt2-2*112x=cnt1
//147-2*112x=cnt1-112*cnt2
//x=(cnt1-112*cnt2)/(147-2*112)
int x=(cnt1-Sblkcnt*cnt2)/(Cblkcnt-2*Sblkcnt);
cntc+=x;
cnts+=(cnt2-2*x);
}
int main(){
char ch;
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> ch;
G[i][j]=(ch=='#'?1:0);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(G[i-1][j]==1 && G[i][j-1]==1 && G[i][j]==0 && vis[i][j]==0){
if(homo_filled(i,j,0,2)!=12){
homo_filled(i,j,2,0);
}
}
}
}
if(G[n][m]==2) homo_filled(n,m,2,0);
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(G[i][j]==1 && vis[i][j]==0){
thist(i,j);
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout << G[i][j] << ' ';
// }
// cout << '\n';
// }
}
}
}
cout << cntc << ' ' << cnts;
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 2292kb
input:
17 17 ......##########. ......##########. ......##########. ......####..####. ......###....###. .......
output:
1 0
result:
ok single line: '1 0'
Test #2:
score: 10
Accepted
time: 0ms
memory: 2292kb
input:
17 17 ...........###... ...........###... ...........###... ...........###... ....##########... .......
output:
0 1
result:
ok single line: '0 1'
Test #3:
score: 10
Accepted
time: 0ms
memory: 2288kb
input:
17 17 ................. ................. ................. ................. .##############.. .###...
output:
0 1
result:
ok single line: '0 1'
Test #4:
score: 10
Accepted
time: 0ms
memory: 2428kb
input:
50 50 ##########...................##############....### ##########...................##############...
output:
1 11
result:
ok single line: '1 11'
Test #5:
score: 10
Accepted
time: 0ms
memory: 2428kb
input:
50 50 ......................###......................... ......................###.....................
output:
5 5
result:
ok single line: '5 5'
Test #6:
score: 10
Accepted
time: 0ms
memory: 2432kb
input:
50 50 ......##########.................................. ......##########.......####################...
output:
7 2
result:
ok single line: '7 2'
Test #7:
score: 10
Accepted
time: 81ms
memory: 6140kb
input:
1000 1000 ##########..##########..##########..##########..##########..##########..##########..######...
output:
4316 0
result:
ok single line: '4316 0'
Test #8:
score: 10
Accepted
time: 91ms
memory: 6164kb
input:
1000 1000 .............................................................................................
output:
539 235
result:
ok single line: '539 235'
Test #9:
score: 10
Accepted
time: 59ms
memory: 6136kb
input:
1000 1000 .............................................................................................
output:
3 7
result:
ok single line: '3 7'
Test #10:
score: 10
Accepted
time: 51ms
memory: 6136kb
input:
1000 1000 .............................................................................................
output:
9 1
result:
ok single line: '9 1'
Extra Test:
score: 0
Extra Test Passed