50分,广搜,WA10个点,求大佬不吝指教
查看原帖
50分,广搜,WA10个点,求大佬不吝指教
155826
明依楼主2019/3/17 21:08
#include<iostream>
#include<queue>
using namespace std;
int n,m,a[1005][1005],b[8]= {1,1,0,-1,-1,-1,0,1},c[8]= {0,1,1,1,0,-1,-1,-1},ans,answer,temp[1005][1005]= {0};
bool p[1005][1005]= {0};
struct egg {
	int x,y;
} qwq;
int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>a[i][j];
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) temp[i][j]=a[i][j];//建立映射(这样才会保证在找数字时不会干扰到搜索其他的数字)
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(!a[i][j]) {
				int num=0;
				for(int d=0; d<8; d++) {
					int xx=i+c[d],yy=j+b[d];
					if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]) {
						num=1;
						break;
					}
				}
				if(num) temp[i][j]=2;//数字
				//0是空格
			}
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(temp[i][j]==2) a[i][j]=2;//返回数字所在的地方
		}
	}
	queue<egg>q;
	for(int j=1; j<=n; j++) {
		for(int g=1; g<=m; g++) {
			if(!a[j][g]&&!p[j][g]) {
				p[j][g]=1;
				qwq.x=j;
				qwq.y=g;
				q.push(qwq);
				while(!q.empty()) {
					egg e=q.front();
					q.pop();
					for(int i=0; i<8; i+=2) {
						int xx=e.x+c[i],yy=e.y+b[i];
						if(xx>0&&xx<=n&&yy>0&&yy<=m&&!a[xx][yy]&&!p[xx][yy]) {
							p[xx][yy]=1;
							qwq.x=xx;
							qwq.y=yy;
							q.push(qwq);
						}
					}
				}
				ans++;
			}
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(a[i][j]==2) {
				int num=0;
				for(int g=0; g<8; g++) {
					int xx=i+c[g],yy=j+b[g];
					if(xx>0&&xx<=n&&yy>0&&yy<=m&&!a[xx][yy]) {
						num=1;
						break;
					}
				}
				if(!num) answer++;
			}
		}
	}
	cout<<answer+ans;
	return 0;
}
//吃货殿下佑我AC此题!!
2019/3/17 21:08
加载中...