欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  网络运营

AtCoder Beginner Contest 176 D-Wizard in Maze(双端队列)

程序员文章站 2022-03-12 07:50:55
Sample Input 1Copy4 41 14 4..#...#..#...#..Sample Output 1Note that he cannot walk diagonally.Sample Input 2Copy4 41 44 1.##.########.##.Sample Output 2Copy-1He cannot move from there.Sample Input 34 42 23 3…………Sample .....

AtCoder Beginner Contest 176  D-Wizard in Maze(双端队列)
AtCoder Beginner Contest 176  D-Wizard in Maze(双端队列)
Sample Input 1
Copy

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

Note that he cannot walk diagonally.

Sample Input 2
Copy

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2
Copy
-1
He cannot move from there.

Sample Input 3

4 4
2 2
3 3



Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5 1 2 2 5
#.###
####.
#…##
#…##

Sample Output 4

2

分析:
对于迷宫类问题显然要用BFS解决。因为要求使用魔法次数最少,所以要尽可能先用A方式移动。

因此BFS时可以采用双端队列,将不使用魔法的状态放队首、使用魔法的状态放队尾。(其实也能用优先队列)

想到这个代码就很好写了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<time.h>
#include<vector>
using namespace std;
struct node
{
    int x,y;
    int step;
};
int h,w,sx,sy,ex,ey;
deque<node> q;
char s[1005][1005],vis[1005][1005];
int nextx[]={0,-1,0,1},nexty[] = {-1,0,1,0};
int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d%d",&h,&w);
    scanf("%d%d",&sx,&sy);
    scanf("%d%d",&ex,&ey);
    for(int i=1; i<=h; ++i){
        for(int j=1; j<=w; ++j)
            scanf(" %c",&s[i][j]);
    }
    /*
    for(int i=1; i<=h; ++i){
        for(int j=1; j<=w; ++j)
            printf("%c",s[i][j]);
        putchar('\n');
    }*/

    vis[sx][sy] = 1;
    q.push_back((node){sx,sy,0});
    //cout<<q.front().x<<' '<<q.front().y;
    //getchar();
    int ans = -1;
    while(!q.empty()){
        struct node t = q.front();
        q.pop_front();
        vis[t.x][t.y] = 1;
        if(t.x==ex&&t.y==ey){
            ans = t.step;
            break;
        }

        for(int i=0; i<4; ++i){
            int tx,ty;
            tx = t.x + nextx[i];
            ty = t.y + nexty[i];
            if(tx>0&&tx<=h&&ty>0&&ty<=w&&s[tx][ty]=='.'&&!vis[tx][ty]){
                q.push_front((node){tx,ty,t.step});
            }
        }

        for(int tx=t.x-2; tx<=t.x+2; ++tx){
            for(int ty=t.y-2; ty<=t.y+2; ++ty){
                if(tx>0&&tx<=h&&ty>0&&ty<=w&&s[tx][ty]=='.'&&!vis[tx][ty]){
                    if(tx==t.x&&ty==t.y)
                        continue;
                    q.push_back((node){tx,ty,t.step+1});
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

本文地址:https://blog.csdn.net/qq_26139541/article/details/108558933

相关标签: atcoder