（深度优先遍历和宽度优先遍历）DFS和BFS（2）

测试通过。

 测试数据：（上图的地形小编已按字符拼接完成，当然也可以自己设置地形啦！）

13 13 3 3
*************
*@@.@@@*@@@.*
***.*@*@*@*@*
*.......*..@*
*@*.***.*@*@*
*@@.@@@.*.@@*
*@*.*@*.*.*.*
**@...@.....*
*@*.*@***.*@*
*...@*@@@.@@*
*@*.*@*@*.*@*
*@@.@@@*@.@@*
*************

其主要的思想就是DFS和BFS。（过程都在题解上写着） 

DFS代码如下（示例）：

#include 
#include 
using namespace std;
//用DFS完成炸d人这一题
//用“@”表示小人，用“*”表示墙，用“.”表示空地 
char a[20][20];
int book[20][20];
int mi,mx,my,m,n;
int Max1(int x,int y)//从（x,y）这个点往四周扩，数一数往四周能炸死几个小人 
{
    
    int i=x,j=y,k=0; 
    while(a[i][y]!='*')
    {
        if(a[i][y]=='@')
        k++;
        i++;
    }
    i=x,j=y;
    while(a[x][j]!='*')
    {
        if(a[x][j]=='@')
        k++;
        j++;
    }
    i=x,j=y;
    while(a[i][y]!='*')
    {
        if(a[i][y]=='@')
        k++;
        i--;
    }
    i=x,j=y;
    while(a[x][j]!='*')
    {
        if(a[x][j]=='@')
        k++;
        j--;
    }
    return k;
} 
void dfs(int x,int y)
{
    int ne[4][2]={{0,1},{1,0},{-1,0},{0,-1}};//可以往上下左右四个方向走
    int tx,ty,sum;
    sum=Max1(x,y);
    if(sum>mi)
    {
        mi=sum;
        mx=x;
        my=y;
    } 
    for(int i=0;i<=3;i++)
    {
        tx=x+ne[i][0];
        ty=y+ne[i][1];
        if(book[tx][ty]==0&&a[tx][ty]=='.')//这个点没有走过，并且这个点是空地，可以安放炸弹
        {
        book[tx][ty]=1;//走过的就将其标记，以后不再走这个位置 
        dfs(tx,ty);//继续寻找下一个位置
         //这里不需要像全排列一样，让book指针回溯，因为我们只需要保证每一个空地试放过一个炸弹就行 
        }
    }     
}
int main()
{
    //输入地图，可以自己设计地图，也可以用图上的那个地图
    /*
    13 13 3 3(13行13列的地图，从（3，3）点开始走)
*************
*@@.@@@*@@@.*
***.*@*@*@*@*
*.......*..@*
*@*.***.*@*@*
*@@.@@@.*.@@*
*@*.*@*.*.*.*
**@...@.....*
*@*.*@***.*@*
*...@*@@@.@@*
*@*.*@*@*.*@*
*@@.@@@*@.@@*
*************
    */ 
    int kx,ky;
    cout<<"请输入图是几行几列" <>m>>n;
    cout<<"请输入起始坐标"<>kx>>ky;
    for(int i=0;i>a[i];
    book[kx][ky]=1;
    mx=kx;
    my=ky;
    mi=Max1(kx,ky);
    dfs(kx,ky);
    cout<<"炸弹放置在点("<

#include 
#include 
using namespace std;
char a[20][20];//用于储存地图
int book[20][20];//用来判断空地是否尝试过放置炸d 
int Max(int x,int y)//从（x,y）这个点往四周扩，数一数往四周能炸死几个小人 
{
	
	int i=x,j=y,k=0; 
	while(a[i][y]!='*')
	{
		if(a[i][y]=='@')
		k++;
		i++;
	}
	i=x,j=y;
	while(a[x][j]!='*')
	{
		if(a[x][j]=='@')
		k++;
		j++;
	}
	i=x,j=y;
	while(a[i][y]!='*')
	{
		if(a[i][y]=='@')
		k++;
		i--;
	}
	i=x,j=y;
	while(a[x][j]!='*')
	{
		if(a[x][j]=='@')
		k++;
		j--;
	}
	return k;
} 
struct kk{
	int x;
	int y;
	int s;
}que[20*20];
int main() 
{
	int kx,ky,m,n;
	cout<<"请输入图是几行几列" <>m>>n;
	cout<<"请输入起始坐标"<>kx>>ky;
	cout<<"请按照规定的符号，输入地形"<>a[i];
	int next[4][2]={{0,1},{1,0},{-1,0},{0,-1}};//可以往上下左右四个方向走
	int mx=kx,my=ky,sum=Max(kx,ky);
	//对队列初始化
	int head=0,tail=0;
	que[tail].x=kx;
	que[tail].y=ky;
	que[tail++].s=0;//现在在（x,y）处，并且步数为0；
	while(headsum)
			 	{
			 		sum=k;
			 		mx=kx;
			 		my=ky;
				}
			 }
		}
		head++;//当某个点的上下左右四个点都判断完后，让头节点出队列，再 判断这个点的四周 
	} 
	cout<<"炸弹放置在点("<

#include 
#include  
using namespace std;
//字符的全排列
char a1[10],b1[10];
int len,book[10];
void dfs(int step)
{
	if(step==len)
	{
	for(int i=0;i>a1;//按照字母的升序从小到大输入
	len=strlen(a1);
	dfs(0);
	return 0;
 }