Blackops

初心易得，始终难守

0%

RQNOJ-83 魔兽世界（BFS+带“传送门”路径的通用方法）

发表于 更新于 分类于 ， ，

题目描述

小A在WOW中是个小术士.作为一名术士,不会单刷副本是相当丢脸的.所谓单刷副本就是单挑BOSS了,这么有荣誉感的事小A怎么会不做呢?于是小A来到了厄运之槌开始了单刷.小A看了看,厄运之槌的地图是一个N*M的矩形（N，M<=100）,上面遍布了小怪和传送门.例如（1表示有小怪，0表示无小怪,大写字母表示传送门,传送门:例如,走到 B 传送门点将传送到另一个 B 传送点（次数无限，但每次进入传送点只传送过去，不会在传送回来）数据保证每个传送门有且仅有相对应的另一个传送门）:

img

而入口在左上方（1，1）,BOSS却躲在右下方（N，M）.小A非常急切的想要完成单刷然后去向其他那些战士啊盗贼啊不会单刷的职业炫耀炫耀,所以呢,小A绝不会在小怪身上浪费时间(当然是绕开他们),并且想通过传送门尽快到达BOSS身边.看啊看,想啊想,还是没找出最快的路.终于,灵机一动,想什么啊,编程呗!

路线如图：

img

[数据规模]

对60%的数据,n,m<=20

对100%的数据,n,m<=100

img

输入格式

第一行2个数据：n m；

下面n行，每行m个数（入口点和BOSS点无怪和传送门），表示厄运之槌的地图。地图数据之间无空格。每步只能走一格，方向上下左右。左上角为入口点,右下角为出口点.

输出格式

一个整数，表示小A最少需要走多少步。如果小A不能走到目标，则输出No Solution.

题目链接：RQNOJ 83

题目本身很简单，个人感觉比较难处理的是进出传送门的情况，比如从一个门进去，另一个门出来，如何分情况做标记。从另一个角度可以发现，传送门的用途总是从一个点传送到另一个点，然后从另一个点继续往外走，那么可以直接合并这两步，不需要传送门之间连边，而是传送门向对应的门的合法邻域内的点连边，这样很简单就将带传送门的搜索问题变成了一般的问题，假如还要求要记录路径，那么把这些特殊的边打上标记，走的时候记录下来就可以了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
//typedef complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 110;
char G[N][N];
struct edge
{
    int to, nxt, w;
    edge() {};
    edge(int _to, int _nxt, int _w): to(_to), nxt(_nxt), w(_w) {};
} E[N * N * 4];
int head[N * N], tot;
int dis[N * N], vis[N * N], dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n, m;
pii trans[27][2];

void init()
{
    clr(head, -1);
    tot = 0;
    for (int i = 0; i < 27; ++i)
        trans[i][0] = trans[i][1] = {-1, -1};
}
inline void add(int s, int t, int w)
{
    E[tot] = edge(t, head[s], w);
    head[s] = tot++;
}
inline bool chk(int x, int y)
{
    return x >= 0 && x < n && y >= 0 && y < m;
}
void spfa(int s)
{
    clr(dis, INF);
    clr(vis, 0);
    deque<int>q;
    q.push_back(s);
    dis[s] = 0;
    vis[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop_front();
        vis[u] = 0;
        for (int i = head[u]; ~i; i = E[i].nxt)
        {
            int v = E[i].to;
            if(dis[v] > dis[u] + E[i].w)
            {
                dis[v] = dis[u] + E[i].w;
                if(!vis[v])
                {
                    if(!q.empty() && dis[v] < dis[q.front()])
                        q.push_front(v);
                    else
                        q.push_back(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main(void)
{
    init();
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", G[i]);
        for (int j = 0; j < m; ++j)
        {
            if(isupper(G[i][j]))
            {
                int x = G[i][j] - 'A';
                if(trans[x][0].first == -1)
                    trans[x][0] = {i, j};
                else
                    trans[x][1] = {i, j};
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if(G[i][j] == '0')
            {
                for (int k = 0; k < 4; ++k)
                {
                    int ii = i + dir[k][0], jj = j + dir[k][1];
                    if(chk(ii, jj) && G[ii][jj] != '1')
                    {
                        add(i * m + j, ii * m + jj, 1);
                    }
                }
            }
            else if(isupper(G[i][j]))
            {
                int x = G[i][j] - 'A';
                if(trans[x][0] == make_pair(i, j))
                {
                    int ii = trans[x][1].first, jj = trans[x][1].second;
                    for (int k = 0; k < 4; ++k)
                    {
                        int iii = ii + dir[k][0], jjj = jj + dir[k][1];
                        if(chk(iii, jjj) && G[iii][jjj] != '1')
                            add(i * m + j, iii * m + jjj, 1);
                    }
                }
                else
                {
                    int ii = trans[x][0].first, jj = trans[x][0].second;
                    for (int k = 0; k < 4; ++k)
                    {
                        int iii = ii + dir[k][0], jjj = jj + dir[k][1];
                        if(chk(iii, jjj) && G[iii][jjj] != '1')
                            add(i * m + j, iii * m + jjj, 1);
                    }
                }
            }
        }
    }
    spfa(0);
    dis[n * m - 1] == INF ? puts("No Solution.") : printf("%d\n", dis[n * m - 1]);
    return 0;
}