社区讨论

50分,广搜,WA10个点,求大佬不吝指教

P4961小埋与扫雷参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@m0nug26b
此快照首次捕获于
2024/09/04 20:37
2 年前
此快照最后确认于
2025/11/21 04:52
4 个月前
查看原帖
C
#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此题!!

回复

3 条回复,欢迎继续交流。

正在加载回复...