# 【CF】B. Conveyor

## [題目連結](https://codeforces.com/group/AXj32pLpIx/contest/468825/problem/B)

## **時間複雜度**

* $O(NM)$

## **解題想法**

這題最關鍵的點是要看出這一題需要使用的解法是 01BFS。

因為可以用 01BFS 解是因為我們可以直接將題目簡化成一張邊權只有 0 和 1 的圖，建圖的方法就是將網格圖上的每個點看成往四個方向延伸的邊，如果你延生出去的方向跟圖上標示的一樣的話那這個邊的邊權就為 0，否則邊權為 1，如果連出去的點是 # 的話，那麼這條邊就不建。

## **完整程式**

/* Question : CF 【2023 MD Player Training】 Simulation Contest 1 - B. Conveyor */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0},     // D
                                            {0, 1},     // R
                                            {-1, 0},    // U
                                            {0, -1} };      // L
const int MAXN = 5000 + 50;
const int N = 30000000 + 7;
int n, m, res;
pii st, ed;
char graph[MAXN][MAXN];
int dis[MAXN][MAXN];
bool vis[MAXN][MAXN];
deque<pii> dq;
string str;
map<char, int> mp;

void bfs(){
    dq.push_front(st);
    mem(dis, -1);
    dis[st.f][st.s] = 0;
    
    while( !dq.empty() ){
        pii cnt = dq.front();
        dq.pop_front();

        if( cnt == ed ) return;
        if( vis[cnt.f][cnt.s] ) continue;
        
        vis[cnt.f][cnt.s] = true;
        int d = dis[cnt.f][cnt.s];
 
        for( int t = 0 ; t < 4 ; t++ ){
            pii nxt = {cnt.f + dir[t].f, cnt.s + dir[t].s};

            if( nxt.s > m || nxt.s <= 0 || nxt.f > n || nxt.f <= 0 ) continue;
            if( graph[nxt.f][nxt.s] == '#' ) continue;

            int nxtd = t != mp[graph[cnt.f][cnt.s]] ? d+1 : d;
            if( dis[nxt.f][nxt.s] == -1 || nxtd < dis[nxt.f][nxt.s] ){
                dis[nxt.f][nxt.s] = nxtd;
                if( t != mp[graph[cnt.f][cnt.s]]) dq.push_back(nxt);
                else dq.push_front(nxt);
            }
        }
    }
}

signed main(){
    opt;
    cin >> n >> m;
    for( int i = 1 ; i <= n ; i++ ){
        cin >> str;
        for( int j = 0 ; j < str.size() ; j++ ) graph[i][j+1] = str[j];
    }
    cin >> st.f >> st.s;
    cin >> ed.f >> ed.s;

    mp['U'] = 2;
    mp['D'] = 0;
    mp['L'] = 3;
    mp['R'] = 1;

    bfs();

    cout << dis[ed.f][ed.s] << "\n";
}