- 1
- /*
- 2 ID: ivorysi
- 3 PROG: camelot
- 4 LANG: C++
- 5 */
- 6#include 7#include 8#include 9#include 10#include 11#include < set > 12#include 13#include < string.h > 14#define siji(i, x, y) for (int i = (x); i <= (y); ++i) 15#define gongzi(j, x, y) for (int j = (x); j >= (y); --j) 16#define xiaosiji(i, x, y) for (int i = (x); i < (y); ++i) 17#define sigongzi(j, x, y) for (int j = (x); j > (y); --j) 18#define inf 0x3f3f3f3f 19#define MAXN 400005 20#define ivorysi 21#define mo 97797977 22#define ha 974711 23#define ba 47 24#define fi first 25#define se second 26#define pii pair 27 using namespace std;
- 28 typedef long long ll;
- 29 int sp[805][2];
- 30 int knivis[805][2];
- 31 int vis[35][35];
- 32 int ksp[805];
- 33 int kingcost[805];
- 34 int r,
- c;
- 35 int ky[8] = {
- 1,
- 2,
- 2,
- 1,
- -1,
- -2,
- -2,
- -1
- };
- 36 int kx[8] = {
- 2,
- 1,
- -1,
- -2,
- -2,
- -1,
- 1,
- 2
- };
- 37 int kj[8] = {
- 1,
- 1,
- 1,
- 0,
- -1,
- -1,
- -1,
- 0
- };
- 38 int ki[8] = {
- 1,
- 0,
- -1,
- -1,
- -1,
- 0,
- 1,
- 1
- };
- 39 struct node {
- 40 int rr,
- cc,
- step;
- 41
- };
- 42 queue q;
- 43 void pre1(int u) {
- 44 memset(vis, 0, sizeof(vis));
- 45 int cx = (u - 1) % c 1,
- rx = (u - 1) / c + 1;
- 46
- while (!q.empty()) q.pop();
- 47 q.push((node) {
- rx,
- cx,
- 0
- });
- 48 vis[rx][cx] = 1;
- 49
- while (!q.empty()) {
- 50 node nw = q.front();
- q.pop();
- 51 kingcost[(nw.rr - 1) * c + nw.cc] = ksp[(nw.rr - 1) * c + nw.cc] = nw.step;
- 52 siji(i, 0, 7) {
- 53 int z = nw.rr + ki[i],
- w = nw.cc + kj[i];
- 54
- if (z <= r && z >= 1 && w <= c && w >= 1 && vis[z][w] == 0) {
- 55 vis[z][w] = 1;
- 56 q.push((node) {
- z,
- w,
- nw.step + 1
- });
- 57
- }
- 58
- }
- 59
- }
- 60
- }
- 61 struct data {
- 62 int rr,
- cc,
- cking,
- step;
- 63 bool operator < (const data & rhs) const {
- 64
- return step > rhs.step;
- 65
- }
- 66
- };
- 67 priority_queue q1;
- 68 void spfa(int u) {
- 69 memset(sp, inf, sizeof(sp));
- 70 memset(knivis, 0, sizeof(vis));
- 71
- while (!q1.empty()) q1.pop();
- 72 int cx = (u - 1) % c 1,
- rx = (u - 1) / c + 1;
- 73 q1.push((data) {
- rx,
- cx,
- 0,
- 0
- });
- 74 sp[u][0] = 0;
- 75 knivis[u][0] = 1;
- 76
- while (!q1.empty()) {
- 77 data nw = q1.top();
- q1.pop();
- 78 siji(i, 0, 7) {
- 79 int z = nw.rr + kx[i],
- w = nw.cc + ky[i];
- 80
- if (z <= r && z >= 1 && w <= c && w >= 1) {
- 81
- if (sp[(z - 1) * c + w][nw.cking] > nw.step + 1) {
- 82 sp[(z - 1) * c + w][nw.cking] = nw.step + 1;
- 83
- if (!knivis[(z - 1) * c + w][nw.cking]) {
- 84 knivis[(z - 1) * c + w][nw.cking] = 1;
- 85 q1.push((data) {
- z,
- w,
- nw.cking,
- nw.step + 1
- });
- 86
- }
- 87
- }
- 88
- }
- 89
- }
- 90
- if (nw.cking == 0 && sp[(nw.rr - 1) * c + nw.cc][1] > nw.step + ksp[(nw.rr - 1) * c + nw.cc]) {
- 91 sp[(nw.rr - 1) * c + nw.cc][1] = nw.step + ksp[(nw.rr - 1) * c + nw.cc];
- 92
- if (!knivis[(nw.rr - 1) * c + nw.cc][1]) {
- 93 knivis[(nw.rr - 1) * c + nw.cc][1] = 1;
- 94 q1.push((data) {
- nw.rr,
- nw.cc,
- 1,
- sp[(nw.rr - 1) * c + nw.cc][1]
- });
- 95
- }
- 96
- }
- 97 knivis[(nw.rr - 1) * c + nw.cc][nw.cking] = 0;
- 98
- }
- 99 100
- }
- 101 int king,
- kni[805],
- cnt;
- 102 int dist[805];
- 103 void init() {
- 104 scanf("%d%d", &r, &c);
- 105 char str[5];
- int b;
- 106 char s;
- 107 scanf("%s%d", str, &b);
- 108 siji(i, 0, 4) if (str[i] >= 'A' && str[i] <= 'Z') {
- s = str[i];
- break;
- }
- 109 king = (b - 1) * c + s - 'A' + 1;
- 110
- while (1) {
- 111 scanf("%s %d", str, &b);
- 112
- if (b == 0) break;
- 113 siji(j, 0, 4) if (str[j] >= 'A' && str[j] <= 'Z') {
- s = str[j];
- break;
- }
- 114 kni[++cnt] = (b - 1) * c + s - 'A' + 1;
- 115 b = 0;
- 116
- }
- 117 pre1(king);
- 118 119
- }
- 120 void solve() {
- 121 init();
- 122 siji(i, 1, cnt) {
- 123 spfa(kni[i]);
- 124 siji(j, 1, r * c) {
- 125
- if (sp[j][0] == inf || dist[j] == -1) {
- dist[j] = -1;
- continue;
- }
- 126 dist[j] += sp[j][0];
- 127 kingcost[j] = min(kingcost[j], sp[j][1] - sp[j][0]);
- 128
- }
- 129
- }
- 130 int ans = inf;
- 131 siji(j, 1, r * c) {
- 132
- if (dist[j] == -1) continue;
- 133 ans = min(kingcost[j] + dist[j], ans);
- 134
- }
- 135 printf("%d\n", ans);
- 136
- }
- 137 int main(int argc, char const * argv[]) 138 {
- 139#ifdef ivorysi 140 freopen("camelot.in", "r", stdin);
- 141 freopen("camelot.out", "w", stdout);
- 142#
- else 143 freopen("f1.in", "r", stdin);
- 144#endif 145 solve();
- 146
- }
来源: