175. 电路维修双端队列广搜类似堆优化dij的双端队列（强行优先）BFS

题目

链接

题解思路

因为走的方向都是呈偶数形式的（对和的损耗），所以无法走到奇数的点。
可以进行特判。

记录这个点往四个方向的情况，走的时候的标志以及地图的对应标志。
当符合地图标识的时候，就无需消耗权值，之间把他入队头。否则入队尾。
这样就强行形成了一个小顶堆。

有堆优化dij的味道了。

每次从队头取出元素来进行松弛操作。每个元素只能用来松弛其他边一次。

最后到n m 的最小费用就被搜索出来了。

AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const  int  INF =  0x3f3f3f3f;

int n , m ;

char mp[510][510] ;
bool st[510][510] ;
int vis[510][510] ;
int dx[4] = { -1 , -1 , 1 , 1 } ;
int dy[4] = { -1 , 1 , 1 , -1 } ;
char di[5] = "\/\/" ;
int xi[4] = { -1 , -1 , 0 , 0 } ;
int yi[4] = { -1 , 0  , 0 , -1 } ;

struct node
{
    int x , y ;
};

int bfs( )
{
    memset( st , 0 , sizeof(st) ) ;
    memset( vis , 0x3f , sizeof(vis) ) ;
    deque  q ;

    q.push_back({0,0}) ;
    vis[0][0] =  0;
    while ( !q.empty())
    {
        node tmp = q.front() ;
        q.pop_front() ;
     //   cout << tmp.x << " " << tmp.y << "n" ;
        if ( tmp.x == n && tmp.y == m )
            return vis[n][m] ;
        if ( st[tmp.x][tmp.y] )
            continue ;
        st[tmp.x][tmp.y] = 1 ;
        for (int i = 0 ; i < 4 ; i++ )
        {
            int fx = tmp.x + dx[i] ;
            int fy = tmp.y + dy[i] ;
            int fxx = tmp.x + xi[i] ;
            int fyy = tmp.y + yi[i] ;
            if ( fx >= 0 && fy >= 0 && fx <= n && fy <= m )
            {
                 if ( mp[fxx][fyy] == di[i] )
                 {
                     if ( vis[fx][fy] > vis[tmp.x][tmp.y])
                     {
                        q.push_front({fx,fy});
                        vis[fx][fy] = vis[tmp.x][tmp.y] ;
                     }
                 }else
                 {
                     if ( vis[fx][fy] > vis[tmp.x][tmp.y] + 1 )
                     {
                        q.push_back({fx,fy});
                        vis[fx][fy] = vis[tmp.x][tmp.y] + 1 ;
                     }
                 }
            }
        }
    }
    return -1 ;
}



int main ()
{
    ios::sync_with_stdio(false);
    int T ;
    cin >> T ;
    while ( T -- )
    {
        cin >> n >> m ;
        for (int i = 0 ; i < n ; i++ )
            cin >> mp[i] ;
        if ( (n + m) % 2 )
            cout << "NO SOLUTIONn" ;
        else
        {
            cout << bfs() << "n" ;
        }
    }

    return 0 ;
}

175. 电路维修 双端队列广搜 类似堆优化dij的 双端队列（强行优先）BFS

C/C++/C#相关栏目本月热门文章

175. 电路维修双端队列广搜类似堆优化dij的双端队列（强行优先）BFS