洛谷 U140282 潜于阴影
题目背景
“退回阴影之中”
题目描述
大主教虽重新集结了部队，但仍然抵挡不住虫群的入侵
他决定带领族人们坐上亚顿之矛，逃离艾尔，前往夏古拉斯——黑暗圣堂武士所在的星球。
已知艾尔（起点）的坐标为（1，1），夏古拉斯（终点）的坐标为（N，M）。而在宇宙中漂浮着大块的陨石，记为“#”，无法通过。其余可通行的位置则记为“.”。亚顿之矛每次行进，仅可向四周四个方向移动一格，这记为一次操作。亚顿之矛拥有一次传送的机会，当在（x,y）处传送时，亚顿之矛会传送至（x+d，y+r）处，使用传送也记为一次操作。
星灵的存亡在此一举，于是大主教找到了你——JDOI滴神。他想知道最少几步操作能到达夏古拉斯。
输入格式
第一行个整数，N,M,d，r,意义在描述已经说明。
接下来 N 行，每行长度是 M，仅有 . 或者 # 的字符串。
输出格式
一个整数，表示最少操作数
若不能到达，则输出-1
题解：
2020.11.14模拟赛T2 95分场。
作法假了...挂了一个点。命好。
我的思路是：裸的走地图BFS是四种方向搜。这个就变成五种方向就行。
但是假了。为什么呢？因为喝药有两种作用，如果不喝药能到，喝药使得步数更少。如果不喝药到不了，喝药使穿墙。所以要分两个部分分别搜索转移。
80pts代码：
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=1010;
int n,m,d,r;
char mp[maxn][maxn];
bool vis[maxn][maxn];
int dis[maxn][maxn];
int dx[]={0,0,0,-1,1,0};
int dy[]={0,1,-1,0,0,0};
struct node
{
int x,y,d;
bool f;
};
queue<node> q;
int main()
{
// freopen("shadow.in","r",stdin);
// freopen("shadow.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&d,&r);
dx[5]=d;
dy[5]=r;
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
if(mp[1][1]=='#')
{
puts("-1");
return 0;
}
node a;
a.x=1,a.y=1,a.d=0,a.f=0;
q.push(a);
vis[1][1]=1;
while(!q.empty())
{
node u=q.front();
q.pop();
if(u.x==n && u.y==m)
{
printf("%d\n",u.d);
return 0;
}
node v;
for(int i=1;i<=5;i++)
{
v.x=u.x+dx[i];
v.y=u.y+dy[i];
v.d=u.d+1;
v.f=u.f;
if(v.x<1 || v.y<1 || v.x>n || v.y>m || mp[v.x][v.y]=='#' || vis[v.x][v.y] || (i==5 && v.f))
continue;
if(i==5)
v.f=1;
q.push(v);
vis[v.x][v.y]=1;
}
}
puts("-1");
return 0;
}
满分代码：
#include <bits/stdc++.h>
#define X x + movx[i]
#define Y y + movy[i]
using namespace std;
bool mapp[2001][2001];
int movx[4] = {1, 0, -1, 0};
int movy[4] = {0, 1, 0, -1};
int n, m;
int a[2001][2001], b[2001][2001];
bool used[2001][2001];
struct hehe{
int x, y;
};
void bfs1()
{
queue < hehe >q;
hehe now;
now.x = now.y = 1;
memset(a, 0x3f, sizeof a);
a[1][1] = 0;
q.push(now);
while(q.size())
{
now = q.front();
q.pop();
int x = now.x, y = now.y;
used[x][y] = 0;
for(int i = 0; i < 4; i++)
{
if(mapp[X][Y] && a[x][y] + 1 < a[X][Y])
{
a[X][Y] = a[x][y] + 1;
if(!used[X][Y])
{
hehe neww;
neww.x = X, neww.y = Y;
q.push(neww);
used[X][Y] = 1;
}
}
}
}
}
void bfs2()
{
queue < hehe >q;
hehe now;
now.x = n;
now.y = m;
memset(b, 0x3f, sizeof b);
memset(used, 0, sizeof used);
b[n][m] = 0;
q.push(now);
while(q.size())
{
now = q.front();
q.pop();
int x = now.x, y = now.y;
used[x][y] = 0;
for(int i = 0; i < 4; i++)
{
if(mapp[X][Y] && b[x][y] + 1 < b[X][Y])
{
b[X][Y] = b[x][y] + 1;
if(!used[X][Y])
{
hehe neww;
neww.x = X, neww.y = Y;
q.push(neww);
used[X][Y] = 1;
}
}
}
}
}
int main()
{
int e, r;
cin >> n >> m >> e >> r;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
char ch;
cin >> ch;
mapp[i][j] = (ch == '.');
}
}
bfs1();
bfs2();
int ans = a[n][m];
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(a[i][j] <= 1000000 && i + e >= 0 && j + r >= 0 && b[i + e][j + r] <= 1000000 && mapp[i + e][j + r])
ans = min(ans, a[i][j] + b[i + e][j + r] + 1);
}
}
if(ans > 1000000 || !mapp[n][m]) cout << -1;
else cout << ans;
return 0;
}