题解 | Bessie's Dream-牛客假日团队赛4C题

C-Bessies Dream_牛客假日团队赛4

https://ac.nowcoder.com/acm/contest/947/C

题目描述

After eating too much fruit in Farmer John's kitchen, Bessie the cow is getting some very strange dreams! In her most recent dream, she is trapped in a maze in the shape of an N×MN×M grid of tiles (1≤N,M≤1,0001≤N,M≤1,000). She starts on the top-left tile and wants to get to the bottom-right tile. When she is standing on a tile, she can potentially move to the adjacent tiles in any of the four cardinal directions.

But wait! Each tile has a color, and each color has a different property! Bessie's head hurts just thinking about it:

If a tile is red, then it is impassable.
If a tile is pink, then it can be walked on normally.
If a tile is orange, then it can be walked on normally, but will make Bessie smell like oranges.
If a tile is blue, then it contains piranhas that will only let Bessie pass if she smells like oranges.
If a tile is purple, then Bessie will slide to the next tile in that direction (unless she is unable to cross it). If this tile is also a purple tile, then Bessie will continue to slide until she lands on a non-purple tile or hits an impassable tile. Sliding through a tile counts as a move. Purple tiles will also remove Bessie's smell.

(If you're confused about purple tiles, the example will illustrate their use.)

Please help Bessie get from the top-left to the bottom-right in as few moves as possible.

输入描述:

The first line has two integers NN and MM, representing the number of rows and columns of the maze.

The next NN lines have MM integers each, representing the maze:

The integer '0' is a red tileThe integer '1' is a pink tileThe integer '2' is an orange tileThe integer '3' is a blue tileThe integer '4' is a purple tile

The top-left and bottom-right integers will always be '1'.

输出描述:

A single integer, representing the minimum number of moves Bessie must use to cross the maze, or -1 if it is impossible to do so.

示例1

输入

4 4
1 0 2 1
1 1 4 1
1 0 4 0
1 3 1 1

输出

10

说明

In this example, Bessie walks one square down and two squares to the right (and then slides one more square to the right). She walks one square up, one square left, and one square down (sliding two more squares down) and finishes by walking one more square right. This is a total of 10 moves (DRRRULDDDR).

解答

注意到每次转移的代价都为一，于是爆搜即可。
这个题的难点在于状态的判重（大概）。
$1000∗1000$ 的数据规模的话map有点勉强，更何况出题人专门出了卡map的数据（第11个点），所以map是无法通过此题的。
我们从状态入手。首先仔细读题，确定出如下状态:

struct state
{
    int x, y;
    int ld; bool smell;
};

考虑到每个状态只有4维，分别是

横坐标
纵坐标
气味
滑行方向

所以我们可以把气味放在十进制下第六位，0-5位放横纵坐标，二进制下的第0位放气味，那么就可以用一个1e7的数组放下所以状态了。

#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e3 + 20;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
inline int read()
{
    int x = 0; char ch = getchar(); bool f = false;
    while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

int N, M;
int a[MAXN][MAXN];
int dis[10000000];
struct state
{
    int x, y;
    int ld; bool smell;
    int idx;
    state(int x, int y, int ld, bool s) :
    x(x), y(y), ld(ld), smell(s) {}
    
    inline void Hash(){
        idx = ((x * 1000 + y + (ld + 1) * 1000000) << 1) | smell;
    }
};

inline bool out(int x, int y){
    return !(1 <= x && x <= N && 1 <= y && y <= M);
}

queue<state> q;
int bfs(){
    state s = state(1, 1, -1, false);
    s.Hash(); q.push(s); dis[s.idx] = 0; 
    while(!q.empty()){
        state u = q.front(); q.pop();
        if(u.x == N && u.y == M) return dis[u.idx];

        if(u.ld != -1){
            state v = u; v.smell = false;
            v.x += dx[u.ld], v.y += dy[u.ld];
            int col = a[v.x][v.y];
            if(!(out(v.x, v.y) || col == 0 || col == 3)){
                if(col != 4) v.ld = -1;
                if(col == 2) v.smell = true;
                v.Hash(); 
                if(dis[v.idx] == -1){
                    q.push(v); dis[v.idx] = dis[u.idx] + 1;
                }
                continue;
            }
            u.ld = -1;
        }

        for(int i = 0; i < 4; i++){
            state v = u; 
            v.x += dx[i], v.y += dy[i];
            int col = a[v.x][v.y];
            if(out(v.x, v.y) || col == 0) continue;
            if(col == 3 && !v.smell) continue;
            if(col == 2) v.smell = true;
            if(col == 4) v.ld = i, v.smell = false;
            v.Hash();
            if(dis[v.idx] == -1){
                q.push(v); dis[v.idx] = dis[u.idx] + 1;
            }
        }
    }
    return -1;
}

int main()
{
    //freopen("p4818.in", "r", stdin);
    memset(dis, 0xff, sizeof(dis));
    cin>>N>>M;
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++) a[i][j] = read();
    cout<<bfs()<<endl;
    return 0;
}

来源：俺是小程