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

牛客网湘潭大学程序设计竞赛F题:maze

程序员文章站 2022-05-24 09:38:24
...

emmmmmmmmmmmmmm因为要写离散作业就没空好好做题,选了两道题(其他不会)做了一下。

F题一个小搜索题,写博客觉得没必要,不写又觉得自己那么久都没做出来。。。。


题意是普通的宽搜加传送魔法阵,所以就应该用更新距离的方式入队列,而不是用vised数组记录。


#include <bits/stdc++.h>
using namespace std;
#define N 301
typedef pair<int, int> P;
#define f first
#define s second
#define INF 0x3f3f3f3f
//bool vis[N * N];
queue<P> que;
char maze[N][N];
int d[N * N];
int n, m, q;
map<P, P> mp;
P tmp1, tmp2;
int sx, sy, tx, ty;
int dx[] = {0, 0, 1, -1, 0};
int dy[] = {1, -1, 0, 0, 0};

int dfs()
{
   // memset(vis, 0, sizeof(vis));
    while(!que.empty()) que.pop();
    memset(d, 0x3f, sizeof(d));
    d[sx * m + sy] = 0;
   // vis[sx * (n - 1) + sy] = true;
    que.push(P(sx, sy));

    P tmp;
    int x, y;

    while(!que.empty()){
        P h = que.front();que.pop();

        x = h.f, y = h.s;
//printf("%d %d\n", x, y);
       if(x == tx && y == ty)
           continue;
         //   return d[x * m + y];

        for(int i = 0; i < 5; i++){
            int xx = x + dx[i], yy = y + dy[i];

            if(maze[xx][yy] == '#' || xx >= n || yy >= m || xx < 0 || yy < 0) continue;

            if(d[x * m + y] + 1 < d[xx * m + yy]){
                d[xx * m + yy] = d[x * m + y] + 1;
                que.push(P(xx, yy));
            }
        }

        tmp.f = x;
        tmp.s = y;
        if(mp.count(tmp) == 1){
            tmp1 = mp[tmp];
            if(maze[tmp1.f][tmp1.s] != '#' && d[tmp1.f * m + tmp1.s] > d[x * m + y] + 3){
                d[tmp1.f * m + tmp1.s] = d[x * m + y] + 3;
                que.push(tmp1);
            }
        }
    }

    if(d[tx * m + ty] < INF) return d[tx * m + ty];
    return -1;
}

int main()
{
   // freopen("date.txt", "r", stdin);
    while(scanf("%d%d%d", &n, &m, &q) != EOF){
        for(int i = 0; i < n; i++){
            scanf("%s", maze[i]);
        }

        mp.clear();
        for(int i = 0; i < q; i++){
            scanf("%d%d%d%d", &tmp1.f, &tmp1.s, &tmp2.f, &tmp2.s);
            mp[tmp1] = tmp2;
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(maze[i][j] == 'S'){
                    sx = i;sy = j;
                }
                else if(maze[i][j] == 'T'){
                    tx = i;ty = j;
                }
            }
        }
        //printf("%d\n", mp.count(P(1, 2)));

        printf("%d\n", dfs());
    }

    return 0;
}


相关标签: 宽度优先搜索