酷暑一夏1

不忘初心,方得始终


洛谷七月月赛B题(3818) 小A和uim之大逃离 II 90分题解

题目

瞬间,地面上出现了一个H行W列的巨幅矩阵,矩阵的每个格子上要么是空地‘.’或者障碍’#’。

他们起点在(1,1),要逃往(H,W)的出口。他们可以一次向上下左右移动一格,这个算一步操作。不过他们还保留着上次冒险时收集的魔液,一口气喝掉后可以瞬移到相对自己位置的(D,R)向量;也就是说,原来的位置是(x,y),然后新的位置是(x+D,y+R),这个也算一步操作,不过他们仅能至多进行一次这种操作(当然可以不喝魔液)。

这个地方是个是非之地。所以他们希望知道最小能有几步操作可以离开这个鬼地方。不过他们可能逃不出这个鬼地方,遇到这种情况,只能等死,别无他法。

题解

BFS,在一般BFS最短路的基础上加上一组魔液,结构体里加一个用没用魔液的标记,然后vis数组分用/没用魔液就好了。第二个点为什么RE我也不知道(:зゝ∠)

代码

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
#include<cstdio>
#include<queue>
const int MAXN=1000+5;
struct data{int x,y,step;bool drink;};
bool map[MAXN][MAXN],vis[MAXN][MAXN][2];int n,m;char inp[MAXN];
int xd[5]={-1,1,0,0,0},yd[5]={0,0,-1,1,0};
std::queue<data>que;
int BFS()
{
data tmp,temp;
tmp.x=1;tmp.y=1;tmp.step=0;tmp.drink=0;
vis[1][1][0]=1;que.push(tmp);
while(!que.empty())
{
temp=que.front();que.pop();
// printf("============%d,%d==========",temp.x,temp.y);
for(int i=0;i<5;i++)
{
if(i==4 && temp.drink) continue;
tmp=temp;
tmp.x+=xd[i];tmp.y+=yd[i];tmp.step++;
// printf("%d,%d : %d %d %d\n",tmp.x,tmp.y,vis[tmp.x][tmp.y][tmp.drink], map[tmp.x][tmp.y] , tmp.x<1 || tmp.y<1 || tmp.x>n || tmp.y>m);
if(i==4) tmp.drink=1;
if(vis[tmp.x][tmp.y][tmp.drink] || map[tmp.x][tmp.y] || tmp.x<1 || tmp.y<1 || tmp.x>n || tmp.y>m) continue;
if(tmp.x==n && tmp.y==m) return tmp.step;
que.push(tmp);
vis[tmp.x][tmp.y][tmp.drink]=1;
}
}
return -1;
}
int main()
{
scanf("%d %d %d %d",&n,&m,&xd[4],&yd[4]);
if(n==1 && m==1)
{
printf("0");
return 0;
}
for(int i=1;i<=n;i++)
{
scanf("%s",inp+1);
for(int j=1;j<=m;j++)
map[i][j]=(inp[j]=='#');
}
printf("%d",BFS());
return 0;
}
最近的文章

Vijos1474 雷曼兔(csapc) 题解

题目这次,OI山成为了雷曼兔那无尽的冒险传说的新舞台!传说OI山中埋藏着巨大的宝藏,伴随着这个传说的是一个迷题:最瑰丽的舞者将达至精灵世界的彼岸……经过仔细推敲,雷曼兔发现这是一个提示宝藏埋藏位置的谜语,在该谜语中指出了一个特定的路径,只有经过了该路径宝藏才会出现,具体情况如下:OI山的地势图可以看 …

于  Vijos, csapc 继续阅读
更早的文章

洛谷七月月赛A题(3817) 小A的糖果题解

题目小A有N个糖果盒,第i个盒中有a[i]颗糖果。 小A每次可以从其中一盒糖果中吃掉一颗,他想知道,要让任意两个相邻的盒子中加起来都只有x颗或以下的糖果,至少得吃掉几颗糖。 题解对于每两个相邻的糖果盒,如果我们假设左边的糖果盒有$a$颗糖果,右边的糖果盒有$b$颗糖果,并且$a+b&gt;x$,那么 …

于  洛谷 继续阅读