Jack's Blog

流淌的心,怎能阻拦,吹来的风,又怎能阻挡。

迷宫问题广度搜索--ACM第五讲

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)

 

迷宫可以以二维数组来存储表示。0表示通路,1表示障碍。注意这里规定移动可以从上、下、左、右四方方向移动。坐标以行和列表示,均从0开始,给定起点(0,0)和终点(4,4),迷宫表示如下:

左图每个方块表示一个状态,浅蓝色的表示遍历了该状态。

广度优先搜索即是按层数一层一层来遍历,先将一层全部扩展,然后再进行下一层。

利用队列先进先出(FIFO)的性质恰好可以来完成这个任务

 

对应的队列的情况:

具体过程:

1 每次取出队列首元素(初始状态),进行拓展

2 然后把拓展所得到的可行状态都放到队列里面

3 将初始状态删除

4 循环执行以上三步直到找到目标状态或者队列为空。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
int mp[10][10];
bool inq[10][10];//passed set true

struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y) {}
};
queue<node> q;
node frm[10][10];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool bfs(){
    q.push(node(1,1));
    inq[1][1]=true;
    frm[1][1]=node(0,0);
    while (!q.empty()){
        node now = q.front();
        q.pop();
        if (now.x==5 && now.y==5){
            return true;
        }
        for(int i=0;i<4;i++){
            int tx=now.x+dx[i],ty=now.y+dy[i];
            if (!inq[tx][ty] && mp[tx][ty]==0){
                inq[tx][ty]=true;
                q.push(node(tx,ty));
                frm[tx][ty]=now;
            }
        }
    }
    return false;
}
void printans(int x,int y){
    if (x==0 && y==0)   return;
    printans(frm[x][y].x,frm[x][y].y);
    printf("(%d, %d)\n",x-1,y-1);
}
int main(){
    for (int i=0;i<=6;i++){
        for (int j=0;j<=6;j++){
            mp[i][j]=-1;
        }
    }
    for (int i=1;i<=5;i++){
        for (int j=1;j<=5;j++){
            scanf("%d",&mp[i][j]);
        }
    }
    bfs();
    printans(5,5);
    return 0;
}

函数的参数是什么样的?
结构体
struct A指针或引用
链表 数组
线性表
链表——无顺序数组
为什么是零散的状态?
1.可以动态申请内存
链表不需要任何静态的申请
eg.1
1 2 3 4 6 8 10
1 2 3 6 8 10
删除第四位
for(int i=3;i<=n;i++){
    a[i]=a[i+1]
}
链表插入一次就好
数组得挪很多次
链表访问比数组麻烦
链表结构体

声明一个指针函数
Struct link{
    int data;
    link* next;(内置类型的一个东西)
}
link *l;
l=new link();
(*l).data=15(l->data=15);
l->next =NULL;
link *head=new link();
link *push_back(link *p,int x)
{
    link *q= new link();
    q->data = x;
    q->next = NULL;
    p->next = q;
    return p->next;

}
Link *tmp = head;

链表访问复杂度较高(频繁插入删除,不频繁查找)
for(int i=1;i<10;i++)
{
    tmp = push_back(tmp,i);
}
栈 stack(抽象数据结构)
只能在顶端进行插入和删除
先进后出
队列(抽象数据结构)
可以用数组,也可用链表
数据结构
1.数据形态
2.数据操作

#include <iostream>

using namespace std;
struct A{
    int a;
    int b;
}A1={0};
struct A my_swap(int a1,int b1)
{
    A1.a=b1;
    A1.b=a1;
    return A1;
}

int main()
{
    int a=1,b=2;
    A A2= my_swap(a,b);
    my_swap(a,b);
    printf("%d %d",a,b);
    return 0;
}

用结构体实现了swap

其实最简单的还是用指针来写swap

my_swap(int &a,int &b)
my_swap(int *a,int *b)
/×
两种写法等价

然而直接用

my_swap(int a,int b);
是不能交换函数值的

因为虽然在这个函数虽然在这个函数内部互换了函数值,但是这仅仅局限与函数内部,对于整个main函数的调用并没有使用返回值。

我在想如果用内联函数进行展开是不是可以交换呢。读者们可以亲自试试。
inline int swap(int a,int b);

 

二分法学习--acm第三讲

Q&A:

什么是二分法呢?

其实一直以来,在我的印象当中就是高中时候求解二元一次方程组解的时候所使用的算法。

也是现代计算器进行计算的原理。(即一直>>1[除以2]直到答案符合精度)

现在,我将通过系统的学习来为大家讲述二分法的更深入的地方。


 

立flag!

我可能真的要脱单了。


华丽分割线

好吧,反正写了也没有人看。说正事了:

要是我成功的脱单了的话,

1.我就每天早上7:00起床背单词

2.晚上10:30上床睡觉

3.学习高级流型微积分,量子力学

4.每天做一道acm题。

----来自一个单身了好几年的工科男的哀叹


更新:脱单失败。。。

1.虽然失败了,但是我依旧会将上述flag实施下来。

2.其实当初内心是不希望脱单成功的,这样的话哪有时间实施我的flag。。。

3.我要减肥,游泳,从下周起不断的完善自己。虽然就像那句老话说的:做最好的自己。不用和谁比,做最好的自己就好!

2017-10-15