题目链接: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<<"\n"; cout<<maxx; return 0; }