dfs46分求调,悬关!
  • 板块P1331 海战
  • 楼主devil_kid
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/8 20:15
  • 上次更新2024/7/8 21:44:35
查看原帖
dfs46分求调,悬关!
968502
devil_kid楼主2024/7/8 20:15

#include<bits/stdc++.h> using namespace std; int r,c; char ch; int mapp[1010][1010]; int dx[4]={0,-1,1,0}; int dy[4]={-1,0,0,1}; int dfs(int x,int y){ mapp[x][y]=2; for(int i=0;i<4;i++){ if(x+dx[i]>0&&x+dx[i]<=r&&y+dy[i]>0&&y+dy[i]<=c&&mapp[x+dx[i]][y+dy[i]]==1)dfs(x+dx[i],y+dy[i]); } } int main(){ cin>>r>>c; int i,j; for(i=1;i<=r;i++){ for(j=1;j<=c;j++){ cin>>ch; if(ch=='#') mapp[i][j]=1;else mapp[i][j]=0; } } int s=0; for(i=1;i<r;i++){ for(j=1;j<c;j++){ if(mapp[i][j]+mapp[i+1][j]+mapp[i][j+1]+mapp[i+1][j+1]==3){ printf("Bad placement."); return 0; } } } for(i=1;i<=r;i++){ for(j=1;j<=c;j++){ if(mapp[i][j]==1){ s++; dfs(i,j); } } } printf("There are %d ships.",s); return 0; }


		cin>>ch;
		if(ch=='#')
		  mapp[i][j]=1;else
		  mapp[i][j]=0;
		}
	}
	int s=0;
	for(i=1;i<r;i++){
		for(j=1;j<c;j++){
			if(mapp[i][j]+mapp[i+1][j]+mapp[i][j+1]+mapp[i+1][j+1]==3){
				printf("Bad placement.");
				return 0;
			}
		}
	}
	for(i=1;i<=r;i++){
		for(j=1;j<=c;j++){
			if(mapp[i][j]==1){
			s++;
			dfs(i,j);	
			}
		}
	}
	printf("There are %d ships.",s);
	return 0;
}
2024/7/8 20:15
加载中...