洛谷 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;
}