救救孩子!dfs的return有问题?内存爆了
  • 板块P1331 海战
  • 楼主今夕何年
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/5/8 16:49
  • 上次更新2023/10/28 01:53:50
查看原帖
救救孩子!dfs的return有问题?内存爆了
122342
今夕何年楼主2022/5/8 16:49
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<limits.h> 
using namespace std;

char boats[1005][1005];
int n,m;
int ans=0;
char by;
int highest=10000,lowest=0;
int leftest=10000,rightest=0;

void dfs(int starti,int startj){//深搜上下左右块,其实只需要向右下 
	
	boats[starti][startj]=='@';//标记当前船块已经搜索过 
	                        //动态维护搜索区域块,以便最后判断是否是实心的 
	lowest=starti>lowest?starti:lowest;
	highest=starti<highest?starti:highest;
	leftest=startj<leftest?startj:leftest;
	rightest=startj>leftest?startj:rightest;
	
	if((starti-1)>0 && boats[starti-1][startj]=='#')//上 
			dfs(starti-1,startj);
	if((startj-1)>0 && boats[starti][startj-1]=='#')//左 
			dfs(starti,startj-1);
	if(starti+1<=n && boats[starti+1][startj]=='#')//下 
			dfs(starti+1,startj);
	if(startj+1<=m && boats[starti][startj+1]=='#')//右 
			dfs(starti,startj+1);
	return;
}

bool check_boat(int highest,int lowest,int leftest,int rightest){
	for(int i=highest;i<=lowest;++i){
		for(int j=leftest;j<=rightest;++j){
			if(boats[i][j]!='@')return false;
		}
	}
	return true;
}//检查深搜过的方块区域里受否是实心的 

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin>>by;
			boats[i][j]=by;
		}
	}//读入数据 ,数据索引最低从 1 开始 
	
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(boats[i][j]=='#'){
				dfs(i,j);//深搜连通块 
				ans++;//索引到一块区域 
				if(!check_boat(highest,lowest,leftest,rightest)){
					cout<<"Bad placement.";
					return 0;
				}//检测该区域是否为实矩形,否则输出 Bad。。。 
				highest=10000;
				lowest=0;
				leftest=10000;
				rightest=0;//初始化,等待记录下一块大区域范围 
			}
		}
	}
	printf("There are %d ships.",ans); 
	return 0;
}
2022/5/8 16:49
加载中...