蒟蒻DFS 91分HELP!
  • 板块P1331 海战
  • 楼主Zouzhuoxuan
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/1/13 15:00
  • 上次更新2023/10/24 04:26:22
查看原帖
蒟蒻DFS 91分HELP!
800322
Zouzhuoxuan楼主2023/1/13 15:00

别跟我说下数据点,因为下不了

#include<bits/stdc++.h>
using namespace std;
char a[1005][1005];
int sum=0,dx[]={0,-1,1,0,0},dy[]={0,0,0,1,-1},n,m;
bool check(int x,int y)
{
	/*
	6 3 5
   2 x 1
	7 4 8
	*/
	char _1=a[x+1][y],_2=a[x-1][y],_3=a[x][y+1],_4=a[x][y-1],_5=a[x+1][y+1],_6=a[x-1][y+1],_7=a[x+1][y-1],_8=a[x-1][y-1];
	bool a1=(_1=='#'),a2=(_2=='#'),a3=(_3=='#'),a4=(_4=='#'),a5=(_5=='#'),a6=(_6=='#'),a7=(_7=='#'),a8=(_8=='#');
	if(a3&&a2&&!a6) return true;
	if(a2&&a4&&!a7) return true;
	if(a4&&a1&&!a8) return true;
	if(a3&&a1&&!a5) return true;
	return false; 
}
void dfs(int x,int y)
{
	if(x<=0||x>n||y<=0||y>m||a[x][y]=='.') return;
	a[x][y]='.';
	if((a[x+1][y]=='#')+(a[x-1][y]=='#')+(a[x][y+1]=='#')+(a[x][y-1]=='#')>=2&&check(x,y))
	{
		printf("Bad placement.\n");
		exit(0);
	}
	for(int i=1;i<=4;i++) dfs(x+dx[i],y+dy[i]);
}
int main()
{
	memset(a,'.',sizeof(a));
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>a[i][j];
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(a[i][j]=='#')
			{
				sum++;
				dfs(i,j);
			}
		}
	}
	printf("There are %d ships.",sum);
}

qql!

2023/1/13 15:00
加载中...