求助大佬,为什么第十个点MLE了
  • 板块P1331 海战
  • 楼主niepandou
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/2/23 19:30
  • 上次更新2023/10/24 00:01:18
查看原帖
求助大佬,为什么第十个点MLE了
856518
niepandou楼主2023/2/23 19:30
#include <iostream>
#include <queue>

using namespace std;

typedef pair<int,int> PII;
const int N = 1010;

int n,m;
int sum;
char sea[N][N];

int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1};

void dfs(int x,int y)
{
	
	if(y == m) 
	{
		dfs(x + 1,0);
		return;	
	} 
	if(x == n)	return; 
	
	if(sea[x][y] == '#')
	{ 
		queue<PII> q;
		q.push({x,y});
		
		//cout<<x<<' '<<y<<endl;
		while(q.size())
		{
			PII t = q.front();
			q.pop();
			
			for(int i = 0;i < 4;++i)
			{
				int xx = t.first + dx[i],yy = t.second + dy[i];
				
				if(xx >= 0 && xx < n && yy >= 0 && yy < m && sea[xx][yy] == '#')
				{	
					sea[xx][yy] = '.';
					q.push({xx,yy});
				}
			}
		}
		++sum;	
	}
	dfs(x,y + 1);//保证每个都要遍历 
}
bool check(int x,int y)
{
	int cnt = 0;
	if(sea[x][y] == '#') cnt++;
	if(sea[x + 1][y] == '#') cnt++;
	if(sea[x][y + 1] == '#') cnt++;
	if(sea[x + 1][y + 1] == '#') cnt++;
	
	if(cnt == 3) return false;
	else return true; 
}
int main()
{
	cin>>n>>m;
	
	for(int i = 0;i < n;++i) cin>>sea[i];
	
	for(int i = 0;i < n;++i)
	{
		for(int j = 0;j < m;++j)
			if(!check(i,j))
			{
				cout<<"Bad placement."<<endl;
				return 0;
			}
	}
	
	
	dfs(0,0);
	cout<<"There are "<<sum<<" ships."<<endl;
	
	
	return 0;
} 
2023/2/23 19:30
加载中...