4.17周末总结

 这个周继续学习搜索内容，做了一些题目来巩固知识

 奇怪的电梯 - 洛谷

 拿到这个题目的时候第一反应就是用广度搜索，尝试的写了一下发现需要记录步数，但是如果用广度搜索的话没法正常记录步数，后来我想了一下那么就写一个数据结构来记录步数

解决这个步数的问题后，队列用结构函数来定义，在使用的过程中，记得步数的逐渐加就解决了

#include
using namespace std;
int e[220];
    struct cord
    {
        int x,y;
    };
int main()
{
 
    int n,a,b,c[220];
    e[a]=1;
    queues;
    cin>>n>>a>>b;
    for(int i=1; i<=n; i++)
        cin>>c[i];
    s.push((cord){a,0});
    cord q;
    while(!s.empty())
    {
        q=s.front();
        s.pop();
        if(q.x==b)
        {
            cout<0&&dis<=n&&e[dis]==0)
            {
                e[dis]=1;s.push((cord){dis,q.y+1});
 
            }
        }
 
        }
cout<<-1;
 
}

[NOIP2017 提高组] 奶酪 - 洛谷

这道题深度优先应该是最快的，首先，找出所有可以从下表面进入的球，然后深度优先搜一遍。一旦遇到一个点最高处高度就，表示可以到上表面，退出。因为每个洞最多访问一次，只需要求是否能到达上表面，而不是最短步数，然后决定下一步的时候还需要O(n)O(n)的时间。所以总复杂度时O(n^2)O(n2)。

实际上，往往不需要访问所有的洞就可以判断“Yes”，大多数情况下只有“No”的情况要访问全部。

#include
const int MAXN=1010;

struct cir
{
    double x,y,z;
    bool operator<(const cir &cpr)const
    {
        return z=h)
    {
        fnd=1;
        return;
    }
    vis[num]=1;
    for(int i=1;i<=n;i++)
    {
        if(fnd)
            return;
        if(!vis[i]&&dist(now.x,now.y,now.z,p[i].x,p[i].y,p[i].z)<=r*2)
            dfs(p[i],i);
    }
    //vis[num]=0;
}

int main()
{
    freopen("cheese.in","r",stdin);
    freopen("cheese.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(p,0,sizeof(p));fnd=0;
        scanf("%d%lf%lf",&n,&h,&r);
        for(int i=1;i<=n;i++)
            scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
        std::sort(p+1,p+n+1);
        for(int i=1;i<=n;i++)//lower
            if(p[i].z-r<=0)
                dfs(p[i],i);
        if(fnd)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

 机器人搬重物 - 洛谷

 读完题目后，得知题目要求我们求出最少时间，这时我们想到要求最少时间往往使用BFS，要注意的是，机器人有体积，bfs时可以将机器人的坐标，这样判断障碍物较为方便，已经访问过的位置（包括横坐标，纵坐标及方向）不可重复访问，可用一个辅助数组来判重。

#include
#define For(a,b,c,d) for(register int a=b;a<=c;a+=d) 
const int my[ 4 ] = { 0 , 1 , 0 , -1 } , mx[ 4 ] = { -1 , 0 , 1 , 0 } ; 
int n , m , maze[ 60 ][ 60 ] ;
bool vis[ 20000 ] ; 
inline int fun( int a , int b , int c ) { return c * 2700 + a * 51 + b ;} 
struct pos { 
    int x , y ; 
    int f ; 
    int mov ; 
} ;
std::queue que ; 
inline bool zq( int x , int y ) { 
    if( maze[ x ][ y ] || maze[ x + 1 ][ y ] || maze[ x ][ y + 1 ] || maze[ x + 1 ][ y + 1 ] )
        return 1 ;
    return 0 ;
}
inline void bfs() {
    int x , y , tx , ty , f , d , mov , lx , ly ;
    char c ;
    scanf("%d %d %d %d %c" , &x , &y , &tx , &ty , &c );
    switch( c ) {
        case 'N': f = 0 ;
            break ;
        case 'E': f = 1 ;
            break ;
        case 'S': f = 2 ;
            break ;
        case 'W': f = 3 ;
            break ;
    }
    pos temp ;
    temp.x = x , temp.y = y , temp.f = f , temp.mov = 0 ;
    que.push( temp ) ;
    while( !que.empty() ) {
        temp = que.front() ;
        que.pop() ;
        x = temp.x , y = temp.y , f = temp.f , d = fun( x , y , f ) , mov = temp.mov ;
        if( x == tx && y == ty ) { 
            printf("%d",mov) ;
            exit( 0 ) ;
        }
        if( vis[ d ] ) 
            continue ;
        vis[ d ] = 1 ;
        temp.mov ++ ;
        temp.f = ( f + 4 - 1 ) % 4 ; 
        que.push( temp ) ;
        temp.f = ( f + 4 + 1 ) % 4 ; 
        que.push( temp ) ;
        temp.f = f ;
        For( i , 1 , 3 , 1 ) { 
            lx = x + mx[ f ] * i , ly = y + my[ f ] * i ;
            if( lx <= 0 || ly <= 0 || lx >= n || ly >= m || zq( lx , ly ) )
                break ;
            temp.x = lx ;
            temp.y = ly ;
            que.push( temp ) ;
        }
    }
    printf("-1");  
}
int main() { 
    scanf("%d %d" , &n , &m ) ;
    For( i , 1 , n , 1 ) {
        For( j , 1 , m , 1 ) {
            scanf("%d", &maze[ i ][ j ] );
        }
    }
    bfs() ;
    return 0;
}

总结：搜索可以解决的问题无非就是两种类型寻找最短路径，寻找次数，比如：1.图形数据中找出全部满足要求的道路 2.图形数据中寻找到达某位在最短的路径是多少 3.寻找图形数据内被封锁的数据 4.数学选择问题，数据相加或相乘，相减求最小次数 *** 作数 5. 在规定的次数内，使数据进行 *** 作，寻找 *** 作后最大值 6.字符串可以相互转化，寻得转为为另一字符的最小交换次数

深搜在使用时一般独立使用，但是在使用时要与部分数学思想集合，总体而言，在确定使用深搜时时最重要的一点是明确题目的思路，考虑好各个细节需要用什么数学思想来解决。

广度搜索在使用时常用构造函数联用，一般用于记录步数，在小部分的题目中需要用数学思想，广搜的题目类型比较固定也就是寻找最小次数，最短路径，还有部分全部次数时也需要用广搜来减少时间复杂度