P3818 小A和uim之大逃离 II

题目背景

话说上回……还是参见 https://www.luogu.org/problem/show?pid=1373 吧

小a和uim再次来到雨林中探险。突然一阵南风吹来,一片乌云从南部天边急涌过来,还伴着一道道闪电,一阵阵雷声。刹那间,狂风大作,乌云布满了天空,紧接着豆大的雨点从天空中打落下来,只见前方出现了一个牛头马面的怪物,低沉着声音说:“呵呵,既然你们来到这,两个都别活了!”。小a和他的小伙伴再次惊呆了!

题目背景

话说上回……还是参见 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列的巨幅矩阵,矩阵的每个格子上要么是空地‘.’或者障碍’#’。

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

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

输入输出格式

输入格式:

 

第一行个整数,H W D R,意义在描述已经说明。

接下来H行,每行长度是W,仅有’.’或者’#’的字符串。

 

输出格式:

 

请输出一个整数表示最小的逃出操作次数。如果他们逃不出来,就输出-1。

 

输入输出格式

输入格式:

 

第一行个整数,H W D R,意义在描述已经说明。

接下来H行,每行长度是W,仅有’.’或者’#’的字符串。

 

输出格式:

 

请输出一个整数表示最小的逃出操作次数。如果他们逃不出来,就输出-1。

 

输入输出样例

输入样例#1:

3 6 2 1
...#..
..##..
..#...

输出样例#1:

5

输入样例#2:

3 7 2 1
..#..#.
.##.##.
.#..#..

输出样例#2:

-1

输入样例#3:

6 6 -2 0
.#....
.#.#..
.####.
.#..#.
.##.#.
....#.

输出样例#3:

21

输入输出样例

输入样例#1:

3 6 2 1
...#..
..##..
..#...

输出样例#1:

5

输入样例#2:

3 7 2 1
..#..#.
.##.##.
.#..#..

输出样例#2:

-1

输入样例#3:

6 6 -2 0
.#....
.#.#..
.####.
.#..#.
.##.#.
....#.

输出样例#3:

21

说明

样例解释1

(1,1)→(1,2)→(1,3)→喝(3,4)→(3,5)→(3,6)

样例解释2

因为只有一瓶魔液所以他们没办法逃出来

样例解释3

D和R还可以是0或者负数。

数据范围与约定

40%的测试数据2<=H,W<=5

70%的测试数据2<=H,W<=100

100%的测试数据2<=H,W<=1000,|D|<H,|R|<W

思路:

  做过一遍,但这次只得了40分。TLE。

  加了vis数组就过了。所以以后不能偷懒。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N=1009;
int H,W,D,R;
char map[N][N];
int ans[2][N][N];
bool vis[2][N][N];
struct node{
    int x;int y;
    int step;
    bool is=0;
};
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
queue<node>q;
const int INF=1e8;
int tot=INF; 
void bfs()
{
    for(int i=1;i<=H;i++)
    for(int j=1;j<=W;j++)
        ans[0][i][j]=ans[1][i][j]=INF;
    node O,to;int x,y;
    O.x=1,O.y=1;O.step=0;O.is=0;
    q.push(O);
    ans[0][1][1]=ans[1][1][1]=0;
    O.is=1;
    q.push(O);
    vis[0][1][1]=vis[1][1][1]=1;
    while(!q.empty())
    {
        O=q.front();q.pop();
        if(O.x==H&&O.y==W)    return ;
        for(int i=0;i<=3;i++)
        {
            x=O.x+dx[i];y=O.y+dy[i];
            if(x<1||x>H||y<1||y>W)    continue;
            if(O.step+1<=ans[O.is][x][y]&&map[x][y]=='.')
            {
                to.x=x,to.y=y,to.step=O.step+1,to.is=O.is;                
                ans[O.is][x][y]=O.step+1;
                if(!vis[O.is][x][y])
                    q.push(to),vis[O.is][x][y]=1;
            }
        }
        if(!O.is)
        {
            x=O.x+D;y=O.y+R;
            if(x<1||x>H||y<1||y>W)    continue;
            if(O.step+1<=ans[1][x][y]&&map[x][y]=='.')
            {
                to.x=x,to.y=y,to.step=O.step+1,to.is=1;            
                ans[1][x][y]=O.step+1;
                if(!vis[1][x][y])
                    q.push(to),vis[1][x][y]=1;
            }
        }
    }
}

int main()
{

    scanf("%d%d%d%d",&H,&W,&D,&R);
    for(int i=1;i<=H;i++)
    for(int j=1;j<=W;j++)
        cin>>map[i][j];
    bfs();
    if(ans[0][H][W])
        tot=min(tot,ans[0][H][W]);
    if(ans[1][H][W])
        tot=min(tot,ans[1][H][W]);
    if(tot!=INF)
    {
        cout<<tot;
        return 0;
    }
    cout<<-1;
    return 0;
}

 

说明

样例解释1

(1,1)→(1,2)→(1,3)→喝(3,4)→(3,5)→(3,6)

样例解释2

因为只有一瓶魔液所以他们没办法逃出来

样例解释3

D和R还可以是0或者负数。

数据范围与约定

40%的测试数据2<=H,W<=5

70%的测试数据2<=H,W<=100

100%的测试数据2<=H,W<=1000,|D|<H,|R|<W

**比赛中MAXN为1010,90分,之后又交了一次100,只是将MAXN改为了2100。。。题目中的数据范围有误QAQ**

题目并不难,就是判重就好,vis前两维记录坐标,第三维记录是否用过药水,然后bfs即可,注意判重。

注意如果一个点用过了药水,则他所有可以扩展的点的状态都是喝过的,就是flag=1,不能再用药水了,不用再搜。

这个点没用过的话,它扩展的点的既有不用的(上下左右),也有用药水的,都要入队。

 1 #include<cstdio>
 2 #include<queue>
 3 #include<iostream>
 4 
 5 using namespace std;
 6 const int MAXN = 2100;
 7 struct node{
 8     int x,y,step;
 9     int flag;
10 }cur,nxt;
11 int dx[6] = {0,0,1,-1};
12 int dy[6] = {1,-1,0,0};
13 char mp[MAXN][MAXN];
14 bool v[MAXN][MAXN][2];
15 int n,m,ax,ay,f;
16 queue<node>q;
17 
18 void bfs()
19 {
20     cur.flag = 0;cur.step = 0;
21     cur.x = 1;cur.y = 1;
22     q.push(cur);
23     v[1][1][0] = true;
24     
25     while (!q.empty())
26     {
27         cur = q.front();
28         q.pop();
29         if (cur.flag == 1) f = 1;
30         else f = 0;
31         for (int i=0; i<4; ++i)
32         {
33             int xx = dx[i]+cur.x;
34             int yy = dy[i]+cur.y;
35             if (xx>0&&xx<=n&&yy>0&&yy<=m&&mp[xx][yy]!='#'&&!v[xx][yy][f])    //是否出界 
36             {
37                 if (xx==n&&yy==m)
38                 {
39                     printf("%d",cur.step+1);
40                     return ;
41                 }
42                 v[xx][yy][f] = true;
43                 nxt.flag = f;nxt.step = cur.step+1;
44                 nxt.x = xx;nxt.y = yy;
45                 q.push(nxt);
46             }
47         }
48         int xx = cur.x+dx[4], yy = cur.y+dy[4];
49         if (f==0&&!v[xx][yy][1]&&xx>0&&xx<=n&&yy>0&&yy<=m&&mp[xx][yy]!='#')
50         {
51             if (xx==n&&yy==m)
52             {
53                 printf("%d",cur.step+1);
54                 return ;
55             }
56             v[xx][yy][1] = true;
57             nxt.flag = 1;nxt.step = cur.step+1;
58             nxt.x = xx;nxt.y = yy;
59             q.push(nxt);
60         }
61     }
62     printf("-1");    
63 }
64 int main()
65 {
66     scanf("%d%d%d%d",&n,&m,&dx[4],&dy[4]);
67     for (int i=1; i<=n; ++i)
68         for (int j=1; j<=m; ++j)
69             cin>>mp[i][j];
70     bfs();
71     return 0;
72 }

 

 

 

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注