看提交记录里别人AC代码又短跑得又快内存又小
我果然是暴力选手
这题直接 bfs 就好了
需要注意的是只记录一个很 simple 的 dst 数组是有问题的
因为可能不同的方向走进同一个格子里代价是一样的，这样会漏掉一个状态
而不同的进入方向会导致下次把这个格子从队列中拿出来更新其他格子的时候出现问题
所以要记录两个 dst (四个也行)：一个是从同行的转移过来的 dst，另一个是从同列的转移过来的 dst (四个就是上下左右了)
代码简单解法自然的题
代码：
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN = 105;
struct STT{
int x, y, dir;
STT(int X = 0, int Y = 0, int DIR = 0) {x = X; y = Y; dir = DIR;}
}bgn, fnl;
int n, m;
char mp[MAXN][MAXN];
int dst[MAXN][MAXN][2];
bool inq[MAXN][MAXN][2];
inline int bfs() {
queue<STT> q;
dst[bgn.x][bgn.y][0] = dst[bgn.x][bgn.y][1] = 0;
int cur = bgn.x - 1;
while(cur && mp[cur][bgn.y] != ‘*‘) {
dst[cur][bgn.y][1] = 0;
q.push(STT(cur, bgn.y, 1));
inq[cur][bgn.y][1] = true;
--cur;
}
cur = bgn.x + 1;
while(cur <= n && mp[cur][bgn.y] != ‘*‘) {
dst[cur][bgn.y][1] = 0;
q.push(STT(cur, bgn.y, 1));
inq[cur][bgn.y][1] = true;
++cur;
}
cur = bgn.y - 1;
while(cur && mp[bgn.x][cur] != ‘*‘) {
dst[bgn.x][cur][0] = 0;
q.push(STT(bgn.x, cur, 0));
inq[bgn.x][cur][0] = true;
--cur;
}
cur = bgn.y + 1;
while(cur <= m && mp[bgn.x][cur] != ‘*‘) {
dst[bgn.x][cur][0] = 0;
q.push(STT(bgn.x, cur, 0));
inq[bgn.x][cur][0] = true;
++cur;
}
while(!q.empty()) {
STT x = q.front(); q.pop(); inq[x.x][x.y][x.dir] = false;
if(x.dir & 1) {
cur = x.x - 1;
while(cur && mp[cur][x.y] != ‘*‘) {
if(dst[x.x][x.y][1] < dst[cur][x.y][1]) {
dst[cur][x.y][1] = dst[x.x][x.y][1];
if(!inq[cur][x.y][1]) {
q.push(STT(cur, x.y, 1));
inq[cur][x.y][1] = true;
}
}
--cur;
}
cur = x.x + 1;
while(cur <= n && mp[cur][x.y] != ‘*‘) {
if(dst[x.x][x.y][1] < dst[cur][x.y][1]) {
dst[cur][x.y][1] = dst[x.x][x.y][1];
if(!inq[cur][x.y][1]) {
q.push(STT(cur, x.y, 1));
inq[cur][x.y][1] = true;
}
}
++cur;
}
if(mp[x.x][x.y + 1] != ‘*‘ && dst[x.x][x.y + 1][0] >= dst[x.x][x.y][1] + 1) {
dst[x.x][x.y + 1][0] = dst[x.x][x.y][1] + 1;
if(!inq[x.x][x.y + 1][0]) {
q.push(STT(x.x, x.y + 1, 0));
inq[x.x][x.y + 1][0] = true;
}
}
if(mp[x.x][x.y - 1] != ‘*‘ && dst[x.x][x.y - 1][0] > dst[x.x][x.y][1] + 1) {
dst[x.x][x.y - 1][0] = dst[x.x][x.y][1] + 1;
if(!inq[x.x][x.y - 1][0]) {
q.push(STT(x.x, x.y - 1, 0));
inq[x.x][x.y - 1][0] = true;
}
}
} else {
cur = x.y - 1;
while(cur && mp[x.x][cur] != ‘*‘) {
if(dst[x.x][x.y][0] < dst[x.x][cur][0]) {
dst[x.x][cur][0] = dst[x.x][x.y][0];
if(!inq[x.x][cur][0]) {
q.push(STT(x.x, cur, 0));
inq[x.x][cur][0] = true;
}
}
--cur;
}
cur = x.y + 1;
while(cur <= m && mp[x.x][cur] != ‘*‘) {
if(dst[x.x][x.y][0] <= dst[x.x][cur][0]) {
dst[x.x][cur][0] = dst[x.x][x.y][0];
if(!inq[x.x][cur][0]) {
q.push(STT(x.x, cur, 0));
inq[x.x][cur][0] = true;
}
}
++cur;
}
if(mp[x.x + 1][x.y] != ‘*‘ && dst[x.x + 1][x.y][1] > dst[x.x][x.y][0] + 1) {
dst[x.x + 1][x.y][1] = dst[x.x][x.y][0] + 1;
if(!inq[x.x + 1][x.y][1]) {
q.push(STT(x.x + 1, x.y, 1));
inq[x.x + 1][x.y][1] = true;
}
}
if(mp[x.x - 1][x.y] != ‘*‘ && dst[x.x - 1][x.y][1] > dst[x.x][x.y][0] + 1) {
dst[x.x - 1][x.y][1] = dst[x.x][x.y][0] + 1;
if(!inq[x.x - 1][x.y][1]) {
q.push(STT(x.x - 1, x.y, 1));
inq[x.x - 1][x.y][1] = true;
}
}
}
}
return min(dst[fnl.x][fnl.y][0], dst[fnl.x][fnl.y][1]);
}
int main() {
scanf("%d%d", &m, &n);
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) dst[i][j][0] = dst[i][j][1] = 0x3f3f3f3f;
for(int i = 1; i <= n; ++i) {
scanf("%s", mp[i] + 1);
for(int j = 1; j <= m; ++j) {
if(mp[i][j] == ‘C‘) {
if(!bgn.x) {
bgn = STT(i, j, 0);
} else {
fnl = STT(i, j, 0);
}
}
}
}
printf("%d\n", bfs());
return 0;
}
BZOJ3393: [Usaco2009 Jan]Laserphones 激光通讯
原文：https://www.cnblogs.com/xcysblog/p/9553142.html