欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

广度优先和深度优先的总结和实践

程序员文章站 2022-07-16 16:02:42
...

题目:一个人在一个坐标放炸弹,请问可以可以杀死的敌人数目最大

我们先将这个地图模型化,墙用#表示,这里有两种墙,一种是可以被炸弹炸掉的,另外一种是不可能被炸掉的。但是由于现在只有一枚炸弹,所以都用#表示,炸弹是不能穿墙的。敌人用G表示,空地用 . 表示,当然炸弹只能放在空地上。
广度优先和深度优先的总结和实践

测试数据:
13 13
#############
#GG.GGG#GGG.#
###.#G#G#G#G#
#…….#..G#
#G#.###.#G#G#
#GG.GGG.#.GG#
#G#.#G#.#.#.#
##G…G…..#
#G#.#G###.#G#
#…G#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############

此题可以用深度优先也可以用广度优先
下面时深度优先的代码:

#include<iostream>
using namespace std;
int book[50][50] = {0};
int next[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; 
char a[50][50];
int n,m;//n为行 m为列
int X,Y,startX,startY,tx,ty,maxx=-1,sign=1; 
int getNum(int x,int y){
    int i=x,j=y,sum=0;//sum用来计数 
    //向下统计可以消灭的敌人数 
    while(a[i][j] != '#'){//判断的点是否为墙,是就继续 
        if(a[i][j] == 'G'){
            sum++;
        } 
        i++;
    } 
    i=x;
    j=y;
    //向右统计可以消灭敌人的人数 
    while(a[i][j] != '#'){
        if(a[i][j] == 'G'){
            sum++;
        } 
        j++;
    }
    i=x;
    j=y;
    //向左统计可以消灭敌人的个数 
    while(a[i][j] != '#'){
        if(a[i][j] == 'G'){
            sum++;
        } 
        j--;
    }
    i=x;
    j=y;
    //向上统计可以消灭敌人的个数 
    while(a[i][j] != '#'){
        if(a[i][j] == 'G'){
            sum++;
        } 
        i--;
    }
    return sum;
} 
void dfs(int x,int y){
        //计算消灭总人数 
        int count = getNum(x,y);
        if(count > maxx){
                maxx = count;
                X = x;
                Y = y;
        } 
        for(int i=0;i<=3;i++){
            if(x < 1 || y < 1 || x > n || y > m){
                continue;
            }
            tx = x+next[i][0];
            ty = y+next[i][1];//右、左、下、上
            //判断是否围墙或者已经走过 
            if(book[tx][ty] == 0 && a[tx][ty] == '.'){
                book[tx][ty] = 1; //标记这个点已走过 
                dfs(tx,ty); //开始尝试下一个点 
            //  book[tx][ty] = 0;
            }            
        } 
        cout<<x<<" "<<y<<endl; 

} 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j]; 
            //初始化开始点 
            if(a[i][j] == '.' && sign == 1 ){
                startX = i;
                startY = j;
                sign = 0;
            } 
        } 
    }   
    dfs(startX,startY);
    cout<<"将炸弹人放置在("<<X-1<<","<<Y-1<<")处,最多可以消灭"<<maxx<<"个敌人"<<endl;
    return 0;
} 

广度优先的代码:

#include<iostream>
using namespace std;
int book[50][50]={0};
char a[50][50];//用来存储地图 
int next[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; 
struct node{
    int x;//横坐标 
    int y;//竖坐标 
}; 
int n,m;//n表示行 m表示列 
struct node que[2501];
int X,Y,tx,ty,flag,sign=1,head=1,tail=1,startX,startY,maxx=-1;

int getNum(int x,int y){
    int i=x,j=y,sum=0;//sum用来计数 
    //向下统计可以消灭的敌人数 
    while(a[i][j] != '#'){//判断的点是否为墙,是就继续 
        if(a[i][j] == 'G'){
            sum++;
        } 
        i++;
    } 
    i=x;
    j=y;
    //向右统计可以消灭敌人的人数 
    while(a[i][j] != '#'){
        if(a[i][j] == 'G'){
            sum++;
        } 
        j++;
    }
    i=x;
    j=y;
    //向左统计可以消灭敌人的个数 
    while(a[i][j] != '#'){
        if(a[i][j] == 'G'){
            sum++;
        } 
        j--;
    }
    i=x;
    j=y;
    //向上统计可以消灭敌人的个数 
    while(a[i][j] != '#'){
        if(a[i][j] == 'G'){
            sum++;
        } 
        i--;
    }
    return sum;
} 
int main(){
    cin>>n>>m;
    //输入地图 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j]; 
            //设置一个开始点 
            if(a[i][j] == '.' && sign == 1 ){
                startX = i;
                startY = j;
                sign = 0;
            } 
        } 
    } 
    //把起始点放到队列中,标记为已经走过的路径 
    que[head].x = startX;
    que[head].y = startY;
    book[startX][startY] = 1; 
    tail++;  
    //当队列不为空是进行循环 
    while(head<tail){
        //枚举四个方向 
        for(int i=0;i<=3;i++){
            //尝试走的下一个下标 
            tx = que[head].x+next[i][0]; 
            ty = que[head].y+next[i][1];
            //判断是否越界 
            if(tx < 1 || ty < 1 || tx > n || ty > m){
                continue;
            }     
            //判断是否为平地或者曾经走过的路 
            if(book[tx][ty] == 0 && a[tx][ty] == '.'){
                //插入新扩展的点到队列中 
                que[tail].x = tx;
                que[tail].y = ty;
                //每个点只入队一次,所以需要标记这个点已经走过 
                book[tx][ty] = 1;
                //统计当前新扩展的点可以消灭的敌人总数 
                int count = getNum(tx,ty); 
                //更新max值和坐标 
                if(count>maxx){
                    maxx = count;
                    X = tx;
                    Y = ty;
                } 
                tail++;
            }  
        } 
        head++;//注意这地方千万不要忘记,当一个点扩展结束后,必须要head++才能对后面的点进行扩展 
    } 
    cout<<"将炸弹人放置在("<<X-1<<","<<Y-1<<")处,最多可以消灭"<<maxx<<"个敌人"<<endl;
    return 0;
} 

总结:虽然深度优先代码少但是本人感觉解决类似像这种迷宫类型的题,使用广度优先会比较方便,容易解答,可以避免一些无谓的bug

相关标签: 搜索算法