题解 U22784 【yizimi的玄学炸弹人】

题目链接：https://www.luogu.org/problemnew/show/U22784

题目

题目背景

yizimi最近喜欢玩一个很玄学的炸弹人游戏

题目描述

在一张n × m（2<n,m<=5000）的地图上，‘#’表示墙，‘*’表示敌人，‘.’表示空地（可以通过或安放炸弹），给出yizimi所在的初始位置（startx,starty），他只可放一颗炸弹，炸弹威力极大，可以同时炸死同一列，同一行的敌人，不过不能穿墙（墙后的敌人炸不死（雾））。问他可以去哪里放炸弹，使得炸死的敌人最多？最多多少？

注意：yizimi不可以往敌人身上撞哟！

感谢凉凉提供数据支持！！！

输入输出格式

输入格式：

第一行：n , m , startx , starty。分别指地图行数、列数、初始位置的坐标 第2~n+1行：输入m个字符，指地图。

输出格式：

第一行输出坐标，用空格空开 第二行输出最多炸死的敌人

说明

20%数据满足：2<n,m<=10

100%数据满足：2<n,m<=5000

总满足1<startx,starty<n

总满足地图最外层为墙

保证yizimi炸死最多的方案唯一（不限定做法）

不保证yizimi可以去到所有空地

题目分析

首先，这是一组迷宫题，别看数据很大，m,n都能到5000，实际上因为只求连通的面积中的大小，直接爆搜就可以了。

算法精析

1.求一个点可以炸死多少敌人

其实就是上下左右四个方向，只要炸到墙，就停止。一个方向的代码如下：

x=i;y=j;//这句话千万别忘了！！！否则就会算成其他行的敌人数
while(a[x][y]!='#'){
	if(a[x--][y]=='*'){//向左的，其余变变方向即可
		sum++;
	} 
} 

2.求连通

用一个DFS去求连通（BFS一样OK啦），每次前进顺便把结果计算一下。

void dfs(int x,int y){
	int tx,ty,k,sum;
	sum=_num(x,y);
	if(sum>maxx){
		maxx=sum;
		mx=x;
		my=y; 
	} 
	for(k=1;k<=4;k++){
		tx=x+next[k][0];
		ty=y+next[k][1];
		if(tx<1 || tx>n || ty<1 || ty>m ){
			continue;
		} 
		if(a[tx][ty]=='.' && !book[tx][ty]){
			book[tx][ty]=1;
			dfs(tx,ty);
		}
	} 
	return;
}

完整代码

有我自己的代码习惯，勿喷
和上面代码有些不同，其实等效

#include<iostream>
#include<string>
#include<iostream>
using namespace std;
#define go(i,j,n,k) for(register int i=j;i<=n;i+=k)
#define fo(i,j,n,k) for(register int i=j;i>=n;i-=k)
#define mn 5010 
char a[mn][mn];
int book[mn][mn]={0};
int maxx,mx,my,n,m;
int next[5][2]={{0,0},{0,1},{1,0},{0,-1},{-1,0}};
inline int _num(int i,int j){
	int sum=0,x,y;
	x=i;y=j;
	while(a[x][y]!='#')
		if(a[x--][y]=='*')
			sum++;
	x=i;y=j;
	while(a[x][y]!='#')
		if(a[x++][y]=='*')
			sum++;
	x=i;y=j;
	while(a[x][y]!='#')
		if(a[x][y--]=='*')
			sum++;
	x=i;y=j;
	while(a[x][y]!='#')
		if(a[x][y++]=='*')
			sum++;
	return sum;
}
inline void dfs(int x,int y){
	int tx,ty,k,sum;
	sum=_num(x,y);
	if(sum>maxx)
		maxx=sum,mx=x,my=y; 
	go(k,1,4,1){
		tx=x+next[k][0];
		ty=y+next[k][1];
		if(tx<1 || tx>n || ty<1 || ty>m )
			continue;
		if(a[tx][ty]=='.' && !book[tx][ty])
			book[tx][ty]=1,dfs(tx,ty);
	} 
	return;
}
int main(){
	int i,j,startx,starty;
	//freopen("yizimi001.in","r",stdin); 
	cin>>n>>m>>startx>>starty;
	go(i,1,n,1)
		go(j,1,m,1)
			cin>>a[i][j];
	book[startx][starty]=1;
	maxx=_num(startx,starty);
	mx=startx,my=starty;
	dfs(startx,starty); 
	cout<<mx<<" "<<my<<"
";
	cout<<maxx; 
	return 0;
}