2019-08-03 课堂总结

BFS 广（宽）度优先搜索

1. luogu P1135 奇怪的电梯

主体思路：

• dfs plus 剪枝 (在显然不可能是最优解时，不继续dfs)
  代码如下：

#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std ;

int n , a , b , cmin = 1000000 , c ;
int num[210] ;
bool flag[210] ;
void dfs(int x , int y)
{
    
    if ( flag[x] == 1 ) return ;
    if ( x == b ) 
    {
        cmin = min(y , cmin) ;
        y = 0 ;
        return ;
    }
    if ( y >= cmin) return ;  //剪枝
    flag[x] = 1 ;
    if ( x > num[x] ) dfs(x - num[x] , y + 1) ;
    if ( x + num[x] <= n ) dfs( x + num[x] , y + 1) ;
    flag[x] = 0 ;
    return ; 
} 
int main()
{
    cin >> n >> a >> b ;
    for ( int i = 1 ; i <= n ; i++)
        cin >> num[i] ;
    dfs(a , 0) ; 
    if ( cmin == 1000000) cmin = -1 ;
    cout << cmin << endl ;
    return 0 ;
}

• bfs的思路：通过一个队列以及结构体，记录到达的步数以及当前数字。
  bfs主体思路：
  每次先有序用上一次生出的节点生成子节点，再继续向下逐层重复以上操作即可得到最优解。
  代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>


using namespace std ;

struct elevator
{
    int f , d ;
};




elevator floor ;
int n , s , t ;
int num[205] ;
bool flag[205] ;
queue<elevator> q ;



int bfs()
{
    q.push((elevator){s , 0}) ;
    while ( q.size())
    {
        floor = q.front() ;
        if ( floor.f == t) return floor.d ;
        q.pop() ;
        flag[floor.f] = true ;
        if ( floor.f + num[floor.f] <= n && !flag[floor.f + num[floor.f]])
        {
            q.push((elevator){floor.f + num[floor.f] , floor.d + 1}) ;
        } 
        if ( floor.f - num[floor.f] >= 1 && !flag[floor.f + num[floor.f]])
        {
            q.push((elevator){floor.f - num[floor.f] , floor.d + 1}) ;
        }
    }
    return -1 ;
}




int main()
{
    scanf("%d%d%d" , &n , &s , &t) ;
    for ( int i = 1 ; i <= n ; i++ )
        scanf("%d" , &num[i]) ;
    printf("%d\n" , bfs()) ;
}

洛谷P1443马的遍历 （没过）

思路：

• bfs直接广搜即可
• dfs感觉也可以，可写完后样例过不去，没查出那里错