广搜求救T-T
  • 板块学术版
  • 楼主RainBow_doge
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/7/18 19:48
  • 上次更新2023/11/3 09:02:59
查看原帖
广搜求救T-T
920244
RainBow_doge楼主2023/7/18 19:48

本蒟蒻用广搜做的,样例过了,为什么过不去(T-T)(题很简单,神犇求勿喷)

/*
题目描述
指挥部被突来的洪水淹没了,还好指挥部有在某些重要的地方起一些围墙,用 * 号表示,而一个封闭的 *号 区域洪水是进不去的……

现在给出指挥部的围墙建设图,问指挥部没被淹到的重要区域(由 0 表示)有多少。

输入
第一行是两个数,x 和 y(x,y≤500)。

第二行及以下是一个由 * 和 0 组成的 x*y 的图。

输出
输出没被水淹没的指挥部的 0 的数量(计算被 * 围住的 0 的个数)。

样例
输入复制
4 5
00000
00*00
0*0*0
00*00
输出复制
1
输入复制
5 5
*****
*0*0*
**0**
*0*0*
*****
输出复制
5
*/
#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;//好习惯 
}
2023/7/18 19:48
加载中...