题目背景
话说上回……还是参见 https://www.luogu.org/problem/show?pid=1373 吧
小a和uim再次来到雨林中探险。突然一阵南风吹来,一片乌云从南部天边急涌过来,还伴着一道道闪电,一阵阵雷声。刹那间,狂风大作,乌云布满了天空,紧接着豆大的雨点从天空中打落下来,只见前方出现了一个牛头马面的怪物,低沉着声音说:“呵呵,既然你们来到这,两个都别活了!”。小a和他的小伙伴再次惊呆了!
题目描述
瞬间,地面上出现了一个H行W列的巨幅矩阵,矩阵的每个格子上要么是空地‘.’或者障碍'#'。
他们起点在(1,1),要逃往(H,W)的出口。他们可以一次向上下左右移动一格,这个算一步操作。不过他们还保留着上次冒险时收集的魔液,一口气喝掉后可以瞬移到相对自己位置的(D,R)向量;也就是说,原来的位置是(x,y),然后新的位置是(x+D,y+R),这个也算一步操作,不过他们仅能至多进行一次这种操作(当然可以不喝魔液)。
这个地方是个是非之地。所以他们希望知道最小能有几步操作可以离开这个鬼地方。不过他们可能逃不出这个鬼地方,遇到这种情况,只能等死,别无他法。
输入输出格式
输入格式:
第一行个整数,H W D R,意义在描述已经说明。
接下来H行,每行长度是W,仅有'.'或者'#'的字符串。
输出格式:
请输出一个整数表示最小的逃出操作次数。如果他们逃不出来,就输出-1。
思路:
其实这道题没有你想象的那么可怕
我们只要广搜即可
我们用一个队列来存走过的长度,目前的位置,还有是否使用过传送
从(1,1)处开始,如果联通,就走
同时,判断此时用不用传送
能传送就传送
如果一个位置以前没走过,就可以走
如果以前是传送过来的,现在不是,也可以走(防止提前传送导致无解)
当然,到达目的地后跳出即可
代码:
#include<iostream> #include<cstdio> #define rii register int i #define rij register int j #define inf 1<<29 using namespace std; int cd,bj[2005][2005],ans,n,m,wz[2005][2005],sd,d,r; struct dl{ int sd,x,y,sy; }z[2000005]; int main() { scanf("%d%d%d%d ",&n,&m,&d,&r); for(rii=1;i<=n;i++) { for(rij=1;j<=m;j++) { char ltt; scanf("%c ",<t); if(ltt=='.') { wz[i][j]=0; } else { wz[i][j]=1; } } } for(rii=1;i<=n;i++) { for(rij=1;j<=m;j++) { bj[i][j]=inf; } } for(rii=0;i<=m+1;i++) { wz[0][i]=1; wz[n+1][i]=1; } for(rii=0;i<=n+1;i++) { wz[i][0]=1; wz[i][m+1]=1; } cd=1; z[1].x=1; z[1].y=1; z[1].sd=0; z[1].sy=1; bj[1][1]=1; for(rii=1;i<=cd;i++) { int ltt=z[i].x; int kkk=z[i].y; if(ltt==n&&kkk==m) { cout<<z[i].sd; break; } if(wz[ltt-1][kkk]!=1) { if(bj[ltt-1][kkk]==inf) { cd++; z[cd].x=ltt-1; z[cd].y=kkk; z[cd].sy=z[i].sy; z[cd].sd=z[i].sd+1; bj[ltt-1][kkk]=z[i].sy; } else { if(bj[ltt-1][kkk]<z[i].sy) { cd++; z[cd].x=ltt-1; z[cd].y=kkk; z[cd].sy=z[i].sy; z[cd].sd=z[i].sd+1; bj[ltt-1][kkk]=z[i].sy; } } } if(wz[ltt+1][kkk]!=1) { if(bj[ltt+1][kkk]==inf) { cd++; z[cd].x=ltt+1; z[cd].y=kkk; z[cd].sd=z[i].sd+1; z[cd].sy=z[i].sy; bj[ltt+1][kkk]=z[i].sy; } else { if(bj[ltt+1][kkk]<z[i].sy) { cd++; z[cd].x=ltt+1; z[cd].y=kkk; z[cd].sd=z[i].sd+1; z[cd].sy=z[i].sy; bj[ltt+1][kkk]=z[i].sy; } } } if(wz[ltt][kkk-1]!=1) { if(bj[ltt][kkk-1]==inf) { cd++; z[cd].x=ltt; z[cd].y=kkk-1; z[cd].sd=z[i].sd+1; bj[ltt][kkk-1]=z[i].sy; z[cd].sy=z[i].sy; } else { if(bj[ltt][kkk-1]<z[i].sy) { cd++; z[cd].x=ltt; z[cd].y=kkk-1; z[cd].sd=z[i].sd+1; bj[ltt][kkk-1]=z[i].sy; z[cd].sy=z[i].sy; } } } if(wz[ltt][kkk+1]!=1) { if(bj[ltt][kkk+1]==inf) { cd++; z[cd].x=ltt; z[cd].y=kkk+1; z[cd].sd=z[i].sd+1; z[cd].sy=z[i].sy; bj[ltt][kkk+1]=z[i].sy; } else { if(bj[ltt][kkk+1]<z[i].sy) { cd++; z[cd].x=ltt; z[cd].y=kkk+1; z[cd].sy=z[i].sy; z[cd].sd=z[i].sd+1; bj[ltt][kkk+1]=z[i].sy; } } } if(wz[ltt+d][kkk+r]!=1&<t+d<=n&<t+d>=1&&kkk+r<=m&&kkk+r>=1&&z[i].sy==1) { z[i].sy--; if(bj[ltt+d][kkk+r]==inf) { cd++; z[cd].x=ltt+d; z[cd].y=kkk+r; z[cd].sd=z[i].sd+1; z[cd].sy=z[i].sy; bj[ltt+d][kkk+r]=z[i].sy; } } if(i==cd) { cout<<"-1"; } } }