No.4.4 再解炸弹人

求解，炸弹放在哪个位置，消灭的僵尸最多？

//G=敌人， .=地面， #=墙壁，炸弹可以向上下左右四个方向无限杀敌，只要不遇到墙壁，位置必须可达，而且只能是地面

一、广度优先搜索

struct node {　　//广优必须有一个队列记录同一层的节点
　　int x;
　　int y;
};
char map[20][20];　　//二维地图

int getsum(int x,int y){　　//对每一个位置，分右、下、左、上四个方向判断可消灭僵尸数
　　int sum=0;
　　int mm,nn;

　　//每个方向判断前，要先回到原始位置，因为只有“.”才会进行此判断，所以下面的 sum++ 不会出现重复计算的问题！

　　mm=x;nn=y;

　　while(map[mm][nn]!='#'){
　　　　if(map[mm][nn]=='G')
　　　　　　sum++;
　　　　nn++;
　　}

　　mm=x;nn=y;
　　while(map[mm][nn]!='#'){
　　　　if(map[mm][nn]=='G')
　　　　　　sum++;
　　　　nn--;
　　}

　　mm=x;nn=y;
　　while(map[mm][nn]!='#'){
　　　　if(map[mm][nn]=='G')
　　　　　　sum++;
　　　　mm++;
　　}

　　mm=x;nn=y;
　　while(map[mm][nn]!='#'){
　　　　if(map[mm][nn]=='G')
　　　　　　sum++;
　　　　mm--;
　　}

　　return sum;
}

int main(){
　　struct node que[401];
　　int head,tail;
　　int book[20][20]={0};
　　int i,j,k,sum,max=0,mx,my,n,m,startx,starty,tx,ty;

　　int next[4][2]={
　　　　{0,1},
　　　　{1,0},
　　　　{0,-1},
　　　　{-1,0}
　　};

　　scanf("%d %d %d %d",&m,&n,&startx,&starty);
　　for(i=0;i 　　　　scanf("%s",map[i]);

　　//初始位置
　　head=1;tail=1;
　　que[tail].x=startx;
　　que[tail].y=starty;
　　tail++;
　　book[startx][starty]=1;
　　max=getsum(startx,starty);
　　mx=startx;

　　my=starty;

　　//广度优先搜索
　　while(head 　　　　for(k=0;k<=3;k++){
　　　　　　tx=que[head].x + next[k][0];
　　　　　　ty=que[head].y + next[k][1];

　　　　　　//符合条件的位置才能入栈，继续进行搜索
　　　　　　if(tx<0 || tx>m-1 || ty<0 || ty>n-1)
　　　　　　　　continue;
　　　　　　if(map[tx][ty]=='.' && book[tx][ty]==0)
　　　　　　{
　　　　　　　　book[tx][ty]=1;
　　　　　　　　que[tail].x=tx;
　　　　　　　　que[tail].y=ty;
　　　　　　　　tail++;

　　　　　　　　sum=getsum(tx,ty);
　　　　　　　　if(sum >max){
　　　　　　　　　　max=sum;
　　　　　　　　　　mx=tx;
　　　　　　　　　　my=ty;
　　　　　　　　}
　　　　　　}
　　　　}
　　head++;　　//子层判断完毕后，父节点出栈，而且不能取消标记 book[][]=1
　　}
　　printf("max=%d,location=(%d,%d)",max,mx,my);
　　getchar();getchar();
　　return 0;
}

二、深度优先搜索：解决当前一步该如何做，然后递归

char map[20][20];
int book[20][20]={0};
int max,mx,my,n,m;　　//记录可消灭僵尸最大值，位置，及二维平面n*m

int getsum(int i,int j){　　//获取当前位置可消灭的僵尸数
　　int sum=0;
　　int x,y;

　　//统计每个方向时，(i,j)总要回归本值，因为传入的值总是map[x][y]=='.'，所以sum不会出现重复++

　　x=i;y=j;　　//下
　　while(map[x][y]!='#'){
　　　　if(map[x][y]=='G')
　　　　　　sum++;
　　　　x++;
　　}

　　x=i;y=j;　　//上
　　while(map[x][y]!='#'){
　　　　if(map[x][y]=='G')
　　　　　　sum++;
　　　　x--;
　　}

　　x=i;y=j;　　//左
　　while(map[x][y]!='#'){
　　　　if(map[x][y]=='G')
　　　　　　sum++;
　　　　y--;
　　}

　　x=i;y=j;　　//右
　　while(map[x][y]!='#'){
　　　　if(map[x][y]=='G')
　　　　　　sum++;
　　　　y++;
　　}

　　return sum;
}

void dfs(int x,int y){　　//解决当前位置该如何做
　　int tx,ty,k;
　　int sum=0;
　　sum=getsum(x,y);
　　if(sum>max){　　//临时获取最值
　　　　max=sum;
　　　　mx=x;
　　　　my=y;
　　}

　　int next[4][2]={
　　　　{0,1},{1,0},
　　　　{0,-1},{-1,0}
　　};

　　for(k=0;k<=3;k++){　　//尝试其他相邻位置
　　　　tx=x+next[k][0];
　　　　ty=y+next[k][1];
　　　　if(tx<0 || tx>n-1 || ty<0 || ty>m-1)
　　　　　　continue;
　　　　if(map[tx][ty]=='.' && book[tx][ty]==0)
　　　　{
　　　　　　book[tx][ty]=1;
　　　　　　dfs(tx,ty);　　//已经尝试的位置不再尝试，故不可取消标记
　　　　}
　　}
　　return ;
}

int main(){
　　int i,startx,starty;

　　scanf("%d %d %d %d",&n,&m,&startx,&starty);
　　for(i=0;i 　　　　scanf("%s",map[i]);　　//注意这里的平面初始化，1.字符串，直接用map，不用&；2.字符串无间隔，故用这种扫描方式

　　book[startx][starty]=1;
　　max=getsum(startx,starty);
　　mx=startx;
　　my=starty;
　　dfs(startx,starty);

　　printf("max=%d,location=(%d,%d)",max,mx,my);
　　getchar();getchar();
　　return 0;
}