算法深度优先搜索和广度优先搜索

#pragma mark - - 深度优先搜索

/**
 * 深度优先搜索基本模型
 * void dfs(int step) {
 *     // 判断边界
 *     ...
 *     return ;
 *     // 尝试每一种可能
 *     for (int i=1; i<=n; i++) {
 *     //继续下一步
 *     dfs(step+1);
 *    }
 *   return ;
 * }
 *
 */

pragma mark - - 数的全排列问题

/*
数的全排列，123的全排列为 123 132 213 231 312 321
那么 1...n的全排列是？
可以把问题类似化为有n个编号为 1~n的盒子和n张编号为 1~n的纸牌，需要把纸牌分别放到盒子里，并且每个盒子里有且仅有一张纸牌
*/

-(void)test1 {
    int a[10]; // 数组a[] 指代小盒子
    int book[10]; // book 数组标记 手牌是否已经用了
    for (int i=1; i<10; i++) {
        a[i] =0;
    }
    
    for (int i=1; i<10; i++) {
        book[i] =0;
    }
    
    func1(1, 8, a, book);

    
}
void func1(int step,int n,int a[],int book[]) {
    // step 表示第几个盒子
    if (step == n+1) {
        // 如果 step == n+1 则表示盒子里的纸牌都已经放完啦 打印
        // 打印数据 输出一组排列 （1~n号盒子里的纸牌的编号）
        int sum=0;
        for (int i=1; i<=n; i++) {
            sum +=a[i]*pow(10, n-i);
        }
        NSLog(@"%d",sum);
        // return 很重要 返回到之前的一步（最近一次调用fun1函数的地方）
        return ;
    }
    
    
    for (int i=1; i<=n; i++) {
        // book[i] ==0 判断纸牌i是否还在手中
        if (book[i]==0) {
            a[step] = i; // 将纸牌i放到编号为step的盒子里
            book[i] = 1; // 将纸牌i标记已经用完
            
            func1(step+1, n, a, book); // 函数递归 放下一个盒子里的纸牌
            book[i] =0; // 回收纸牌 一定要把之前的纸牌回收 才能进行下一次放牌
            
        }
    }
    
    return ;
}

pragma mark - - 填数使等式成立问题

/*
___ + ___ = ___ 在下划线上填上1~9，每个数字只能使用一次，使等式成立。
有多少种填法
*/

/*
假设有9张牌和9个盒子a[]，把牌放到盒子里，每个盒子里只放一张牌
最后判断a[1]100+a[2]10+a[3] + a[4]100+a[5]10+a[6] == a[7]100+a[8]10+a[9]
*/

int total;

-(void)test2 {
    int a[10],book[10];
    int step=1;
    for (int i=1; i<10; i++) {
        a[i] =0;
    }
    
    for (int i=1; i<10; i++) {
        book[i] =0;
    }
    
    total=0;
    func2(step, a, book);
    NSLog(@"共%d种",total);
  
}

void func2(int step,int a[],int book[]) {
    int n=9;
    if (step==n+1) {
        if (a[1]*100+a[2]*10+a[3] + a[4]*100+a[5]*10+a[6] == a[7]*100+a[8]*10+a[9]) {
            //打印结果
            NSLog(@"%d%d%d+%d%d%d=%d%d%d",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
            total++;
        }
        return ;
    }
    
    
    
    for (int i=1; i<=n; i++) {
        if (book[i]==0) {
            a[step] = i;
            book[i] = 1;
            // 继续下一步
            func2(step+1, a, book);
            book[i]=0;
            
        }
    }
    
    return ;
}

pragma mark - -迷宫问题（深度优先搜索）

/*
有这样一个地图
0,0,1,0,
0,0,0,0,
0,0,1,0,
0,1,0,0,
0,0,0,1

1代表障碍物，0代表空地~
起点为0,0;目的地为3,2
从起点到终点的最短距离？
最短距离的路径？

// 初始化 栈 存储路径
struct note {
    int x; // 横坐标
    int y; // 纵坐标
};

struct note s[100];
int top=0;
int min;

-(void)test3 {
    int a[5][4] = {0,0,1,0,
                   0,0,0,0,
                   0,0,1,0,
                   0,1,0,0,
                   0,0,0,1 };
    
    int book[10][10];
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            book[i][j] =0;
        }
    }
    
    // 起始点
    int x=0,y=0;
    // 目标点
    int p=2,q=3;
    
    // 步数
    int step=0;
    
    // 初始化min
    min=1000;
    book[0][0]=1;
    func3(x, y, 5, 4, a, book, step, p, q,0,0);
    NSLog(@"最短距离:%d",min);
   
}

void func3(int x,int y,int m,int n,int a[5][4],int book[10][10],int step,int p,int q,int tx,int ty) {
    // x,y 为当前位置 起点为0，0
    // m,n 为地图的行数 列数 对应x，y
    // a[][] 地图 book[] 标记数组 标记该点是否已经走过 走过为1
    // step 当前步
    // p q 目标点
    // 方向数组 右 下 左 上
    int next[4][2] ={{0,1},//向右
                     {1,0},//向下
                     {0,-1},//向左
                     {-1,0}};//向上
    
    if (tx==p && ty ==q) {
        if (step<min) {
            min = step;
            // 打印 路径
            for (int i=1; i<=top; i++) {
                NSLog(@"(%d,%d)",s[i].x,s[i].y);
            }
            
        }
        return ;
    }
    
    // 枚举4种走法
    for (int k=0; k<4; k++) {
        tx =x+next[k][0];
        ty =y+next[k][1];
        // 判断是否越界
        if (tx<0||tx>m-1||ty<0||ty>n-1) {
            continue ;
        }
        // 判断是否为障碍物或者已经走过(避免走重复路径)
        if (a[tx][ty]==0 && book[tx][ty]==0) {
            // 入栈
            top++;
            s[top].x=tx;
            s[top].y=ty;
            
            book[tx][ty]=1; // 标记为已走
            func3(tx, ty, m, n, a, book, step+1,p,q,tx,ty); // 下一步
            book[tx][ty]=0; // 尝试结束 取消这个点的标记
            
            // 出栈
            top--;
            
        }
    }
    
    return;
    
}

pragma mark - - 炸弹人问题（深度优先搜索）

/*
 有地图如下：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#
 #############
 
 .表示空地，G表示敌人，#表示墙
 炸弹人当前位置为（3,3）,请问炸弹人走到什么位置放下炸弹能炸死最多敌人（炸弹的爆炸方向是 竖直和水平方向，不可以过墙）
 
 */


int maxsum;
int maxx;
int maxy;

-(void)test4 {
    
    char a[13][13] = { '#','#','#','#','#','#','#','#','#','#','#','#','#',
        '#','G','G','.','G','G','G','#','G','G','G','.','#',
        '#','#','#','.','#','G','#','G','#','G','#','G','#',
        '#','.','.','.','.','.','.','.','#','.','.','G','#',
        '#','G','#','.','#','#','#','.','#','G','#','G','#',
        '#','G','G','.','G','G','G','.','#','.','G','G','#',
        '#','G','#','.','#','G','#','.','#','.','#','.','#',
        '#','#','G','.','.','.','G','.','.','.','.','.','#',
        '#','G','#','.','#','G','#','#','#','.','#','G','#',
        '#','.','.','.','G','#','G','G','G','.','G','G','#',
        '#','G','#','.','#','G','#','G','#','.','#','G','#',
        '#','G','G','.','G','G','G','#','G','.','G','G','#',
        '#','#','#','#','#','#','#','#','#','#','#','#','#', };
    
    int book[13][13]={0};
    int x=3;
    int y=3;
    int step=0;
    
    maxsum =0;
    func4(step, book, a, x, y);
    NSLog(@"在（%d,%d）处可以炸死的敌人最多，最多为%d",maxx,maxy,maxsum);
    
}

void func4(int step,int book[13][13],char a[13][13],int x,int y) {
    
    // 初始化方向 数组
    int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    
    int m=13;// 行数
    int n=13;// 列数
    
    // 下一点 坐标
    int tx,ty;
    
    // 计算当前点所能炸死的敌人数
    int sum = getnum(x, y, a);
    if (sum>maxsum) {
        maxsum =sum;
        maxx =x;
        maxy =y;
    }
    for (int k=0; k<4; k++) {
        
        tx = x+next[k][0];
        ty = y+next[k][1];
        
        // 判断边界
        if (tx<0||tx>m-1||ty<0||ty>n-1) {
            continue ;
        }
        
        // 判断当前点是否为空地 并且没在路径中
        if (a[tx][ty]=='.' && book[tx][ty]==0) {
            
            book[tx][ty] =1;
            func4(step+1, book, a, tx, ty);
            book[tx][ty] =0;
        }
        
    }
    
    return ;
    
}

pragma mark - - 广度优先搜索

/*
用一个队列存储所有可以到达的点
从一个点出发，把所有下一次可以到达的点加入队列里，然后 head++，继续执行，直到找到目的点
*/

pragma mark - - 迷宫问题（广度优先搜索）

/*
有这样一个地图
0,0,1,0,
0,0,0,0,
0,0,1,0,
0,1,0,0,
0,0,0,1

1代表障碍物，0代表空地~
起点为0,0;目的地为3,2
从起点到终点的最短距离？
最短距离的路径？
*/

-(void)test5 {
    struct note1 {
        int x;
        int y;
        int s; // 步数
        int f; // 父亲在队列中的编号，即当前节点 是由哪一个节点过来
    };
    
    struct note1 que[2500]; // 队列
    
    int a[5][4] = {0,0,1,0,
        0,0,0,0,
        0,0,1,0,
        0,1,0,0,
        0,0,0,1 };
    
    int book[10][10];
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            book[i][j] =0;
        }
    }
    
    int m =5;
    int n =4;
    
    // 起始点
    int x=0,y=0;
    // 目标点
    int p=2,q=3;
    
    // 初始化 队列
    int head=1;
    int tail=1;
    
    // 初始化方向数组
    int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    
    // 将起点加入队列
    que[tail].x =x;
    que[tail].y =y;
    que[tail].s =0;
    que[tail].f =0;
    tail ++;
    book[x][y] =1;
    
    // 循环队列
    int tx,ty;
    int flag=0; // 标记是否找到目的地
    while (head<tail) {
        // 枚举4个方向
        for (int k=0; k<4; k++) {
            // 计算下一节点的坐标 下一个节点是由当前head节点扩展来的
            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 (a[tx][ty]==0&&book[tx][ty]==0) {
                // 入队 入队的这个节点点是有当前head延伸出来的
                que[tail].x =tx;
                que[tail].y =ty;
                que[tail].s =que[head].s+1;
                que[tail].f =head;
                tail ++;
                // 标记 每个点只入队一次
                book[tx][ty] =1;
                // 如果找到目标点，停止扩展，退出for循环，并且标记，以便退出while循环，结束任务
                if (tx==p&&ty==q) {
                    flag =1;
                    break;
                }
                
            }
        }
        
        if (flag==1) {
            break;
        }
        head ++; // 当一个点扩展结束，head++才能继续执行队列，扩展其他点
    }
    
    NSLog(@"最短距离:%d",que[tail-1].s);
    // 打印路径
    // 初始化 栈 存储路径
    struct note1 route[100];
    top=0;
    
    int lastIndex = tail-1;
    while (lastIndex!=1) {
        //  入栈
        top++;
        route[top].x =que[lastIndex].x;
        route[top].y =que[lastIndex].y;
        route[top].s =que[lastIndex].s;
        route[top].f =que[lastIndex].f;
        
        // 上一个节点
        lastIndex = que[lastIndex].f;
    }
    
    while (top!=0) {
        NSLog(@"(%d,%d)",route[top].x,route[top].y);
        // 出栈
        top--;
    }
}

pragma mark - - 炸弹人问题（广度优先搜索）

/*
    有地图如下：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#
 #############
 
 .表示空地，G表示敌人，#表示墙
 炸弹人当前位置为（3,3）,请问炸弹人走到什么位置放下炸弹能炸死最多敌人（炸弹的爆炸方向是 竖直和水平方向，不可以过墙）
 
 */

/*
广度优先搜索，将所有炸弹人可以到达的点加到队列里，计算每一个点可以炸死的敌人
*/


-(void)test6 {
    char a[13][13] = { '#','#','#','#','#','#','#','#','#','#','#','#','#',
                       '#','G','G','.','G','G','G','#','G','G','G','.','#',
                       '#','#','#','.','#','G','#','G','#','G','#','G','#',
                       '#','.','.','.','.','.','.','.','#','.','.','G','#',
                       '#','G','#','.','#','#','#','.','#','G','#','G','#',
                       '#','G','G','.','G','G','G','.','#','.','G','G','#',
                       '#','G','#','.','#','G','#','.','#','.','#','.','#',
                       '#','#','G','.','.','.','G','.','.','.','.','.','#',
                       '#','G','#','.','#','G','#','#','#','.','#','G','#',
                       '#','.','.','.','G','#','G','G','G','.','G','G','#',
                       '#','G','#','.','#','G','#','G','#','.','#','G','#',
                       '#','G','G','.','G','G','G','#','G','.','G','G','#',
                       '#','#','#','#','#','#','#','#','#','#','#','#','#', };
    
    
    int book[13][13]={0};
    
    int max =0; // 统计该点能炸死多少敌人
    int mx = 0;
    int my = 0;
    int mtail=0; // 记录最大点时 在队列中的位置
    
    int m=13; //  行数
    int n=13; //  列数
    
    int x=3;
    int y=3;
    
    // 初始化 方向数组
    int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    
    //初始化队列
    struct mapnote {
        int x;
        int y;
        int f; // 记录上一个节点在队列里的位置
        int s; // 步数
    };
    struct mapnote que[400];
    int head=1;
    int tail=1;
    
    // 入队 起点
    que[tail].x=x;
    que[tail].y=y;
    que[tail].s=0;
    que[tail].f=0;
    tail ++;
    // 把起点标记为已走 每个点只入队一次
    book[x][y] =1;
    
    // 下一个节点的位置
    int tx,ty;
    
    while (head<tail) {
        
        for (int k=0; k<4; k++) {
            // 下一个节点 是有 当前head节点扩展的
            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 (a[tx][ty]=='.' && book[tx][ty]==0) {
                // 入队
                que[tail].x =tx;
                que[tail].y =ty;
                que[tail].s =que[head].s+1;
                que[tail].f =head;
                tail ++;
                // 标记为已入队列
                book[tx][ty] =1;
                
                // 计算炸死敌人数
                int sum =getnum(tx, ty, a);
                if (sum>max) {
                    max =sum;
                    // 记录当前位置
                    mx =tx;
                    my =ty;
                    
                    mtail =tail-1;
                }
                
                
                
            }
        }
        
        head ++; //当前节点扩展结束，head++，才能继续对后面的点进行扩展
        
        
    }
    
    
    NSLog(@"在（%d,%d）处可以炸死的敌人最多，最多为%d",mx,my,max);
    
    // 打印步数
    NSLog(@"需要%d步",que[mtail].s);
    
    // 打印路径
    struct mapnote route[100];
    top=0;
    
    int lastIndex =mtail;
    while (lastIndex!=0) {

        // 入栈
        top++;
        route[top].x =que[lastIndex].x;
        route[top].y =que[lastIndex].y;
        route[top].s =que[lastIndex].s;
        route[top].f =que[lastIndex].f;
        
        lastIndex =que[lastIndex].f;
    }
    
    while (top!=0) {
        NSLog(@"(%d,%d)",route[top].x,route[top].y);
        top--;
    }
    

    
}

int getnum(int i,int j,char a[13][13]) {
    int sum=0;
    int x,y;
    // 每次计算该方向所能炸死的敌人时，都要把x,y置初始值
    //上
    x=i;
    y=j;
    while (a[x][y]!='#') {
        if (a[x][y]=='G') {
            sum++;
        }
        
        x--;
    }
    
    // 下
    x=i;
    y=j;
    while (a[x][y]!='#') {
        if (a[x][y]=='G') {
            sum ++;
        }
        x++;
    }
    
    // 右
    x=i;
    y=j;
    while (a[x][y]!='#') {
        if (a[x][y]=='G') {
            sum ++;
        }
        y++;
    }
    
    // 左
    x=i;
    y=j;
    while (a[x][y]!='#') {
        if (a[x][y]=='G') {
            sum ++;
        }
        y--;
    }
    
    return sum;
}

pragma mark - - 宝岛探险问题

/*
有地图如下：

1,2,1,0,0,0,0,0,2,3
3,0,2,0,1,2,1,0,1,2
4,0,1,0,1,2,3,2,0,1
3,2,0,0,0,1,2,4,0,0
0,0,0,0,0,0,1,5,3,0
0,1,2,1,0,1,5,4,3,0
0,1,2,3,1,3,6,2,1,0
0,0,3,4,8,9,7,5,0,0
0,0,0,3,7,8,6,0,1,2
0,0,0,0,0,0,0,0,1,0

0代表海水 1~9代表陆地的海拔
小明当前的位置在（6，8）;请问小明所在的岛面积为多少？
*/

/*
广度优先搜索，从起点开始，每次从上下左右4个方向扩展，当扩展到的点大于0时加入队列，直到队列扩展完毕，所有被加入到队列的点的总数就是小岛的面积
*/

-(void)test7 {
    // 地图
    int a[10][10] ={ 1,2,1,0,0,0,0,0,2,3,
                     3,0,2,0,1,2,1,0,1,2,
                     4,0,1,0,1,2,3,2,0,1,
                     3,2,0,0,0,1,2,4,0,0,
                     0,0,0,0,0,0,1,5,3,0,
                     0,1,2,1,0,1,5,4,3,0,
                     0,1,2,3,1,3,6,2,1,0,
                     0,0,3,4,8,9,7,5,0,0,
                     0,0,0,3,7,8,6,0,1,2,
                     0,0,0,0,0,0,0,0,1,0 };
    
    // 起点
    int x=6;
    int y=8;
    // 下一点
    int tx;
    int ty;
    int m=10; // 行数
    int n=10; // 列数
   
    struct mapnote {
        int x;
        int y;
    };
    
    struct mapnote que[400];
    // 标记 是否加入队列
    int book[10][10] = {0};
    
    //  初始化 方向数组
    int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    
    // 初始化队列
    int head=1;
    int tail=1;
    // 起点 入队
    que[tail].x = x;
    que[tail].y = y;
    tail ++;
    book[x][y] =1;
    
    while (head<tail) {
        
        for (int k=0; k<4; 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 (a[tx][ty]>0 && book[tx][ty] == 0) {
                // 入队
                que[tail].x =tx;
                que[tail].y =ty;
                tail ++;
                
                // 一定要标记 避免重复路径
                book[tx][ty] =1;
            }
        }
        
        head ++;
    }
    
    NSLog(@"小明该小岛的面积为:%d",tail-1);
}

pragma mark - - 宝岛探险问题2 （广度优先搜索）

/*
有地图如下：

1,2,1,0,0,0,0,0,2,3
3,0,2,0,1,2,1,0,1,2
4,0,1,0,1,2,3,2,0,1
3,2,0,0,0,1,2,4,0,0
0,0,0,0,0,0,1,5,3,0
0,1,2,1,0,1,5,4,3,0
0,1,2,3,1,3,6,2,1,0
0,0,3,4,8,9,7,5,0,0
0,0,0,3,7,8,6,0,1,2
0,0,0,0,0,0,0,0,1,0

0代表海水 1~9代表陆地的海拔
该地图上有多少个小岛，面积是多少？
*/

-(void)test8 {
    // 地图
    int a[10][10] ={ 1,2,1,0,0,0,0,0,2,3,
        3,0,2,0,1,2,1,0,1,2,
        4,0,1,0,1,2,3,2,0,1,
        3,2,0,0,0,1,2,4,0,0,
        0,0,0,0,0,0,1,5,3,0,
        0,1,2,1,0,1,5,4,3,0,
        0,1,2,3,1,3,6,2,1,0,
        0,0,3,4,8,9,7,5,0,0,
        0,0,0,3,7,8,6,0,1,2,
        0,0,0,0,0,0,0,0,1,0 };
    
    // 下一点
    int tx;
    int ty;
    int m=10; // 行数
    int n=10; // 列数
    
    int area=0;
    
    struct mapnote {
        int x;
        int y;
    };
    
    
    // 标记 是否加入队列
    int book[10][10] = {0};
    
    //  初始化 方向数组
    int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            
            // 判断当前点 是否是陆地 以及 是否已经入队
            if (book[i][j]==1 || a[i][j]==0) {
                continue ;
            }
            
            // 对小岛编号（着色）
            area--;
            
            // 初始化队列
            struct mapnote que[400];
            int head=1;
            int tail=1;
            
            // 把当前点加到队列里
            que[tail].x =i;
            que[tail].y =j;
            tail ++;
            book[i][j] =1;
            // 地图着色
            a[i][j] =area;
            
            while (head<tail) {
                
                for (int k=0; k<4; 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 (a[tx][ty]>0 && book[tx][ty] == 0) {
                        // 地图着色
                        a[tx][ty] = area;
                        
                        book[tx][ty] = 1;
                        // 入队
                        que[tail].x= tx;
                        que[tail].y= ty;
                        tail ++;
                    }
                }
                
                head ++ ;
                
            }
            
            NSLog(@"编号为%d的小岛面积为%d ",area,tail-1);
            
        }
    }
    
    //  打印着色后的地图
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            printf("%3d",a[i][j]);
        }
        printf("\n");
    }
    
}

pragma mark - - 宝岛探险问题2 （深度优先搜索）

/*
有地图如下：

1,2,1,0,0,0,0,0,2,3
3,0,2,0,1,2,1,0,1,2
4,0,1,0,1,2,3,2,0,1
3,2,0,0,0,1,2,4,0,0
0,0,0,0,0,0,1,5,3,0
0,1,2,1,0,1,5,4,3,0
0,1,2,3,1,3,6,2,1,0
0,0,3,4,8,9,7,5,0,0
0,0,0,3,7,8,6,0,1,2
0,0,0,0,0,0,0,0,1,0

0代表海水 1~9代表陆地的海拔
该地图上有多少个小岛，面积是多少？
*/

int areasum =0;
-(void)test9 {
    // 地图
    int a[10][10] ={ 1,2,1,0,0,0,0,0,2,3,
        3,0,2,0,1,2,1,0,1,2,
        4,0,1,0,1,2,3,2,0,1,
        3,2,0,0,0,1,2,4,0,0,
        0,0,0,0,0,0,1,5,3,0,
        0,1,2,1,0,1,5,4,3,0,
        0,1,2,3,1,3,6,2,1,0,
        0,0,3,4,8,9,7,5,0,0,
        0,0,0,3,7,8,6,0,1,2,
        0,0,0,0,0,0,0,0,1,0 };
    
    int book[10][10]={0};
    

    int area=0;
    
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            if (a[i][j]>0) {
                area --;
                int step =0;
                areasum =1;
                book[i][j] =1;
                func9(step, a, book, i, j,area);
                NSLog(@"编号为%d的小岛的面积为%d",area,areasum);
        
            }
        }
    }
    
    // 打印着色地图
    for (int i=0; i<10; i++) {
        for (int j=0; j<10; j++) {
            printf("%3d",a[i][j]);
        }
        printf("\n");
    }
    
}


void func9 (int step,int a[10][10],int book[10][10],int x,int y,int area) {
    //  初始化 方向数组
    int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
    int tx,ty;
    int m=10; // 行数
    int n=10; // 列数
    
    // 当前点 着色
    a[x][y] =area;
    
    // 遍历方向
    for (int k=0;k<4; k++) {
        tx = x+next[k][0];
        ty = y+next[k][1];
        if (tx<0||tx>m-1||ty<0||ty>n-1) {
            continue ;
        }
        if (a[tx][ty]>0&&book[tx][ty]==0) {
            book[tx][ty]=1;
            areasum++;
            func9(step+1, a, book, tx, ty,area);
        }
        
    }
    
}

最后编辑于：2019.04.15 15:07:46

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 222,252评论 6赞 516
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 94,886评论 3赞 399
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 168,814评论 0赞 361
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,869评论 1赞 299
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,888评论 6赞 398
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 52,475评论 1赞 312
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 41,010评论 3赞 422
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,924评论 0赞 277
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,469评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,552评论 3赞 342
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,680评论 1赞 353
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 36,362评论 5赞 351
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 42,037评论 3赞 335
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,519评论 0赞 25
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,621评论 1赞 274
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 49,099评论 3赞 378
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,691评论 2赞 361

算法 深度优先搜索和广度优先搜索

pragma mark - - 数的全排列问题

pragma mark - - 填数使等式成立 问题

pragma mark - -迷宫问题（深度优先搜索）

pragma mark - - 炸弹人问题（深度优先搜索）

pragma mark - - 广度优先搜索

pragma mark - - 迷宫问题（广度优先搜索）

pragma mark - - 炸弹人问题（广度优先搜索）

pragma mark - - 宝岛探险问题

pragma mark - - 宝岛探险 问题2 （广度优先搜索）

pragma mark - - 宝岛探险 问题2 （深度优先搜索）

推荐阅读更多精彩内容

算法深度优先搜索和广度优先搜索

pragma mark - - 填数使等式成立问题

pragma mark - - 宝岛探险问题2 （广度优先搜索）

pragma mark - - 宝岛探险问题2 （深度优先搜索）