P1506
样例过了,但只有三十分(我是蒟蒻,神犇勿喷)
#include<bits/stdc++.h>
using namespace std;
//最近练广搜,看到这道题发现以前做过类似的,就搬过来了,结果样例过了,就是不对T-T
int n,m;
char a[510][510];
int b[6100000][3];//广搜路径
int fx[5]={0,0,1,0,-1}; //右下左上
int fy[5]={0,1,0,-1,0};
int rear=1,head=1;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
int tx;
int ty;
//绕圈式搜索,确保不落下一个,搜不到的地方一定被包了(试过好几个,很蒻的结论。。。。)
for(int i=1;i<=n;i++){
if(a[i][1]=='0'){
head=1;
rear=1;
b[1][1]=i;
b[1][2]=1;
a[i][1]='*';//把搜到的都变成围墙
while(head<=rear){
for(int i=1;i<=4;i++){
tx=b[head][1]+fx[i];
ty=b[head][2]+fy[i];
if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&a[tx][ty]=='0'){
rear++;
a[tx][ty]='*';
b[rear][1]=tx;
b[rear][2]=ty;
}
}
head++;
}
}
}
for(int i=1;i<=m;i++){
if(a[1][i]=='0'){
head=1;
rear=1;
b[1][1]=1;
b[1][2]=i;
a[1][i]='*';
while(head<=rear){
for(int i=1;i<=4;i++){
tx=b[head][1]+fx[i];
ty=b[head][2]+fy[i];
if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&a[tx][ty]=='0'){
rear++;
a[tx][ty]='*';
b[rear][1]=tx;
b[rear][2]=ty;
}
}
head++;
}
}
}
for(int i=1;i<=m;i++){
if(a[n][i]=='0'){
head=1;
rear=1;
b[1][1]=n;
b[1][2]=i;
a[n][i]='*';
while(head<=rear){
for(int i=1;i<=4;i++){
tx=b[head][1]+fx[i];
ty=b[head][2]+fy[i];
if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&a[tx][ty]=='0'){
rear++;
a[tx][ty]='*';
b[rear][1]=tx;
b[rear][2]=ty;
}
}
head++;
}
}
}
for(int i=1;i<=n;i++){
if(a[i][m]=='0'){
head=1;
rear=1;
b[1][1]=i;
b[1][2]=m;
a[i][m]='*';
while(head<=rear){
for(int i=1;i<=4;i++){
tx=b[head][1]+fx[i];
ty=b[head][2]+fy[i];
if(tx>=1&&ty>=1&&tx<=n&&ty<=n&&a[tx][ty]=='0'){
rear++;
a[tx][ty]='*';
b[rear][1]=tx;
b[rear][2]=ty;
}
}
head++;
}
}
}
//搜到的都变成围墙了,把0计数输出
int k=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='0'){
k++;
}
}
}
cout<<k;
//样例过了,但就是对不了
return 0;//好习惯
}