c++ 孤岛营救问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了c++ 孤岛营救问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3105字，纯文字阅读大概需要5分钟。

内容图文

孤岛营救问题

题目描述

1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为N 行，东西方向被划分为M列，于是整个迷宫被划分为 N×M 个单元。每一个单元的位置可用一个有序数对(单元的行号，单元的列号)来表示。南北或东西方向相邻的 2 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成 P类，打开同一类的门的钥匙相同，不同类门的钥匙不同。
大兵瑞恩被关押在迷宫的东南角，即(N，M)单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入(1，1)单元。另外，麦克从一个单元移动到另一个相邻单元的时间为1，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。
试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

输入

第 1行有 3个整数，分别表示N,M,P的值。［均小于等于10］
第 2 行是1个整数 K[小于等于150]，表示迷宫中门和墙的总数。
第 I+2 行（1<=I<=K） ，有 5 个整数，依次为Xi1,Yi1,Xi2,Yi2,Gi： 当Gi>=1时，表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间有一扇第Gi类的门，当 Gi=0时，表示(Xi1,Yi1)单元与(Xi2,Yi2)单元之间有一堵不可逾越的墙（其中，|Xi1-Xi2|+|Yi1-Yi2|=1，0<=Gi<=P） 。
第K+3行是一个整数S，表示迷宫中存放的钥匙总数。
第K+3+J 行(1<=J<=S)，有3个整数， 依次为Xi1,Yi1,Qi： 表示第J 把钥匙存放在(Xi1,Yi1)单元里，并且第J 把钥匙是用来开启第Qi类门的。 （其中 1<=Qi<=P） 。
输入数据中同一行各相邻整数之间用一个空格分隔。

输出

程序运行结束时，将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解，则输出-1。

样例输入

4 4 9 
9 
1 2 1 3 2 
1 2 2 2 0 
2 1 2 2 0 
2 1 3 1 0 
2 3 3 3 0 
2 4 3 4 1 
3 2 3 3 0 
3 3 4 3 0 
4 3 4 4 0 
2 
2 1 2 
4 2 1 

样例输出

14

提示

存在一个格子有多把钥匙的情况

AC代码

#include <stdio.h>
#include <string.h>

int n,m,p,k;
int d[11][11][11][11];
int kn,g[11][11][100],gn[11][11];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct point
{
    char x,y;
    int step;
    bool key[11];
};
int fun(point u)
{
    int ans = 0,p = 1;
    for (int i = 1;i <= 10;i ++)
    {
        ans += p * u.key[i];
        p = p * 2;
    }
    return ans;
}
point q[650000],s;
bool used[11][11][1024];
int f,e;
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    scanf("%d",&k);
    memset(used,0,sizeof(used));
    memset(g,0,sizeof(g));
    for(int i=1;i<=k;i++)
    {
        int a1,b1,a2,b2;
        scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
        scanf("%d",&d[a1][b1][a2][b2]);
        if(d[a1][b1][a2][b2]==0)
            d[a1][b1][a2][b2]=-1;
        d[a2][b2][a1][b1]=d[a1][b1][a2][b2];
    }
    scanf("%d",&kn);
    memset(gn,0,sizeof(gn));
    for(int i=1;i<=kn;i++)
    {
        int a1,b1;
        scanf("%d%d",&a1,&b1);
        gn[a1][b1]++;
        scanf("%d",&g[a1][b1][gn[a1][b1]]);
    }
    s.x=1,s.y=1,s.step=0;
    memset(s.key,0,sizeof(s.key));
    q[1]=s;
    int f=1,e=1;
    while(f<=e)
    {
        point u=q[f++];
        for(int i=0;i<4;i++)
        {
            point v=u;
            v.x=u.x+dx[i];
            v.y=u.y+dy[i];
            v.step=u.step+1;
            memcpy(v.key,u.key,sizeof(u.key));
            if(v.x<1||v.x>n||v.y<1||v.y>m)continue;
            if(d[u.x][u.y][v.x][v.y]==-1)continue;
            if (used[v.x][v.y][fun(v)] == 1) continue;
            if(d[u.x][u.y][v.x][v.y]>0)
            {
                if(u.key[d[u.x][u.y][v.x][v.y]]==0)continue;
            }
            if(gn[v.x][v.y]>0)
            {
                for(int j=1;j<=gn[v.x][v.y];j++)
                v.key[g[v.x][v.y][j]]=1;
            }
            if(v.x==n&&v.y==m)
            {
                printf("%d\n",v.step);
                return 0;
            }
            e++;
            q[e]=v;
            used[v.x][v.y][fun(v)] = 1;
        }
    }
    printf("-1\n");
    return 0;
}

(未完待续)

内容总结

以上是互联网集市为您收集整理的c++ 孤岛营救问题全部内容，希望文章能够帮你解决c++ 孤岛营救问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端