UVA 1601 The Morning after Halloween

Wesley13
• 阅读 674

https://vjudge.net/problem/UVA-1601

题目

你在游乐场的鬼屋里当操作员,专门控制鬼屋里的机器人……某日没事干的出题人把这些机器人搬到了其他地方,你需要在最短的时间内遥控机器人让他们回到原位。所有机器人都可以同时在1秒内朝四个方向(上下左右)移动1格,但是每次移动都必须符合以下条件

  1. 每个格子只能有一个机器人
  2. 任意两个机器人的位置不能交换
  3. 不能移动到墙里……

问你需要至少多少时间才能把所有机器人归位。

输入包含多组数据

地图的宽、高和机器人的数量

下面几行表示地图,其中小写字母表示机器人的位置,大写字母表示机器人的终点,'#'表示墙,' '表示可以走的位置……

输出每组数据下的最短时间

样例输入

5 5 2
#####
#A#B#
#   #
#b#a#
#####
16 4 3
################
## ########## ##
#    ABCcba    #
################
16 16 3
################
### ##    #   ##
##  #  ##   # c#
#  ## ########b#
# ##  # #   #  #
#   # ##  # # ##
## a# #   # #  #
### ## #### ## #
##   #   #  #  #
#  ##### # ## ##
####   #B# #   #
##  C#   #   ###
#  # # ####### #
# ######  A##  #
#        #    ##
################
0 0 0

样例输出

7
36
77

 题解

只用了一个单向bfs,对空格编号建图,用前向星……

检测能否互换需要分n=2和n=3两种情况考虑

n=2时很简单

n=3时要考虑$\binom{3}{2}$种情况,头晕还多想了3个位置都换了的情况,其实这是不可能的,由于只能移动一步,所以加上这个这只是浪费时间……
UVA 1601 The Morning after Halloween

AC代码(1080ms,去掉浪费时间的部分是750ms)

#include<bits/stdc++.h>
using namespace std;
#define REP(i,x,y) for(register int i=(x); i<(y); i++)
#define REPE(i,x,y) for(register int i=(x); i<=(y); i++)
#ifdef sahdsg
#define DBG(a,...) printf(a, ##__VA_ARGS__)
#else
#define DBG(a,...) (void)0
#endif

#define MAXN 20
#define MAXP 300
int w,h,n;
int cnt;
int mp[MAXN][MAXN];
int st[3],ed[3];
bool vis[MAXP][MAXP][MAXP];
int hed[131072], nxt[131072], poi[131072], fstar=0;
inline void conn(int f, int t) {
    nxt[fstar]=hed[f];
    poi[fstar]=t;
    hed[f]=fstar++;
}
struct node {
    int s;
    int p[3];
    node(int *x, int y=0):s(y) {memcpy(p,x,sizeof p);}
};
inline void bfs() {
    memset(vis,0,sizeof vis);
    queue<node> q;
    q.push(node(st));
    int ans=-1;
    while(!q.empty()) {
        node now = q.front();q.pop();
        if(memcmp(now.p,ed,sizeof ed)==0) {ans=now.s; break;}
        int i[3],k[3],dis[3];
        REP(i,0,n) dis[i]=now.p[i];
        memset(k,0,sizeof k);
        #define CHK k[0]!=k[1] && k[1]!=k[2] && k[2]!=k[0]
        for(i[0]=hed[now.p[0]]; ~i[0]; i[0]=nxt[i[0]]) {
            k[0]=poi[i[0]];
            if(n>=2) for(i[1]=hed[now.p[1]]; ~i[1]; i[1]=nxt[i[1]]) {
                k[1]=poi[i[1]];
                if(n>=3) for(i[2]=hed[now.p[2]]; ~i[2]; i[2]=nxt[i[2]]){
                    k[2]=poi[i[2]];
                    if(!vis[k[0]][k[1]][k[2]]) if(CHK) {
                        if(dis[0]==k[1] && dis[1]==k[0]) continue;
                        if(dis[0]==k[2] && dis[2]==k[0]) continue;
                        if(dis[1]==k[2] && dis[2]==k[1]) continue;
                        
                        int j[3],l[3];
                        memcpy(j,k,sizeof j);memcpy(l,dis,sizeof j);
                        sort(j,j+3);sort(l,l+3);
                        if(memcmp(j,l,sizeof j)==0) continue;
                        vis[k[0]][k[1]][k[2]]=1;
                        q.push(node(k,now.s+1));
                    }
                }
                else if(!vis[k[0]][k[1]][0]) if(k[0]!=k[1]) {
                    if(k[0]==dis[1] && k[1]==dis[0]) continue;
                    vis[k[0]][k[1]][0]=1; q.push(node(k,now.s+1));
                }
            } else if(!vis[k[0]][0][0]){vis[k[0]][0][0]=1; q.push(node(k,now.s+1));}
        }
    }
    printf("%d\n", ans);
}
int main() {
    #ifdef sahdsg
    freopen("in.txt", "r", stdin);
    #endif
    while(~scanf("%d%d%d", &w, &h, &n) && w) {
        cnt=0;
        memset(hed,-1,sizeof hed);
        memset(st,0,sizeof st);
        memset(ed,0,sizeof ed);
        fstar=0;
        REP(i,0,h) REP(j,0,w) {
            char ch = getchar();
            if(ch<' ')ch=getchar();
            if(ch=='#') {mp[i][j]=-1; continue;}
            mp[i][j]=cnt;
            if(ch>='a' && ch<='z') st[ch-'a']=cnt;
            else if(ch>='A' && ch<='Z') ed[ch-'A']=cnt;
            conn(cnt,cnt);
            if(i>0 && mp[i-1][j]>=0) conn(mp[i-1][j],cnt),conn(cnt,mp[i-1][j]);
            if(j>0 && mp[i][j-1]>=0) conn(mp[i][j-1],cnt),conn(cnt,mp[i][j-1]);
            cnt++;
        }
        bfs();
    }
    
    return 0;
}

 比较慢,可以用双向bfs或A*优化……

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
ROS的安装与使用
一、apt方式安装安装说起ROS,可能大家现在或多或少都有所了解。现如今世界机器人发展之迅猛犹如几十年前计算机行业一样,机器人也逐渐进入到千家万户,大到工业机器人,小到家用的服务型机器人,各式各样,为各种人们生活所需的机器人以计算机技术的发展为基础的机器人也是如雨后春笋。机器人可主要分为硬件层和软件层两个大的主要方向。每一种
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
ROS和Gazebo进行机器人仿真(一)
Gazebo是一种多机器人仿真器,可用于室内外机器人仿真。Gazebo在ROS中有良好的接口,包含ROS和Gazebo的所有控制。若要实现ROS到Gazebo的通信,我们必须安装ROSGazebo接口。应该安装以下软件包:$sudoaptinstallrosmelodicgazeborospkgs rosmelodicga
Stella981 Stella981
3年前
Android蓝牙连接汽车OBD设备
//设备连接public class BluetoothConnect implements Runnable {    private static final UUID CONNECT_UUID  UUID.fromString("0000110100001000800000805F9B34FB");
你需要知道的 10 大互联网爬虫
机器人和僵尸网络通常与网络犯罪分子窃取数据、身份、信用卡号码和更糟糕的情况有关。但是,机器人也可以有好的目的。将好的机器人与坏的机器人区分开来,也可以在保护你公司的网站和确保你的网站获得应有的互联网流量方面发挥很大作用。大多数好的机器人基本上都是世界上最大的网站派出的爬虫,为其搜索引擎和社交媒体平台索引内容。你想让这些机器人访问你。它们会给你带来更多的访问量