题目

Description

Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……

这次魔王汲取了上次的教训，把Ignatius关在一个n*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试,Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。

Input

每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图，其中包括:

. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙，对应的门分别为A-J

每组测试数据之间有一个空行。

Output

针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开，如果不能则输出-1。

Sample Input

4 5 17
@A.B.
a*.*.
*..*^
c..b*

4 5 16
@A.B.
a*.*.
*..*^
c..b*

Sample Output

16
-1

题解

总觉得上面背景里的意思和样例不一样……

这种错觉导致的问题就是，理解错了题意

最初理解的是：在t时间后传送回初始位置，但是不会死，而是继续寻路(可以在t时间内拿到钥匙，开t时间距离的门，即使钥匙距离大于t/2)

在这个错误的思路下，写出了一个错误的答案，不知道能不能“AC”

不过也算一种相似题型的思路吧

/*
    HDU 1429.胜利大逃亡(续) 的错误理解
    
    理解为：t时间后强行传送到起点(不结束，还能继续走)
*/

/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)


const int maxn = 25;
char Map[maxn][maxn];
int dis[maxn][maxn];
int n,m,t;
typedef pair<int,int> point;
const int delta[] = {1,-1,0,0};

int BFS(int s1,int s2,int v1,int v2) {
    queue<point> Q,door;
    memset(dis,-1,sizeof(dis));

    bool key[10];
    memset(key,false,sizeof(key));

    Q.push(point(s1,s2));
    dis[s1][s2] = 0;

    while(!Q.empty() || !door.empty()) {
        if(!Q.empty()) {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();

            REP(4) {
                int xx = x + delta[o];
                int yy = y + delta[3 - o];

                //非法访问
                if(xx < 0 || xx >= n || yy < 0 || yy >= m)
                    continue;
                //墙
                if(Map[xx][yy] == '*')
                    continue;
                //钥匙
                if(Map[xx][yy] >= 'a' && Map[xx][yy] <= 'j')
                    key[Map[xx][yy] - 'a'] = true;
                //门
                if(Map[xx][yy] >= 'A' && Map[xx][yy] <= 'J')
                    if(!key[Map[xx][yy] - 'A'])
                        door.push(point(xx,yy));

                //更新节点
                int temp = dis[xx][yy];
                dis[xx][yy] = (dis[xx][yy] == -1 ? dis[x][y] + 1 : min(dis[x][y] + 1,dis[xx][yy]));
                //剪枝：如果已超过时间，就不再考虑
                if(dis[xx][yy] >= t)
                    continue;
                if(temp != dis[xx][yy])
                    Q.push(point(xx,yy));
            }
        } else {
            int size = door.size();
            bool flag = false;
            while(size--) {
                int x = door.front().first;
                int y = door.front().second;
                door.pop();
                if(key[Map[x][y] - 'A']) {
                    Q.push(point(x,y));
                    flag = true;
                    break;
                }
                door.push(point(x,y));
            }
            if(flag)
                continue;
            else
                break;
        }
    }
    return dis[v1][v2];
}

bool Do() {
    if(scanf("%d%d%d",&n,&m,&t) == EOF)
        return false;

    int s1,s2,v1,v2;
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++) {
            scanf("\n%c\n",&Map[i][j]);
            if(Map[i][j] == '@') {
                s1 = i;
                s2 = j;
            }
            if(Map[i][j] == '^') {
                v1 = i;
                v2 = j;
            }
        }

    printf("%d\n",BFS(s1,s2,v1,v2));

    return true;
}

int main() {
    while(Do());
    return 0;
}

换回正确思路，我们发现，需要保存有哪些钥匙

对于a-j 10把钥匙，我们共有1024种可能

因此，我们可以采用二进制来记录钥匙的集合

//返回新的钥匙集合 
//参数：原始的钥匙集合 获得的钥匙的编号
inline int get_key(int key,int num) {
    return key | (1 << num);
}

//返回是否存在门的钥匙
//参数：钥匙集合 门的编号
inline bool has_key(int key,int num) {
    return (key & (1 << num)) > 0;
}

然后看成3维空间的BFS，层数代表钥匙的集合

由于可能有1024层，因此要即时剪枝

(觉得会有更好的算法来解决吧，整个三维数组开出来有640000，略大)

另外，晚上真的不适合做题……

删错行，把if当成while找bug……

代码

/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)


const int maxn = 25;
char Map[maxn][maxn];
int dis[maxn][maxn][1024];
int n,m,t;
const int delta[] = {1,-1,0,0};

struct point {
    int x,y;
    int key;
    point(int a,int b,int c) {
        x = a;
        y = b;
        key = c;
    }
};

//返回新的钥匙集合 
//参数：原始的钥匙集合 获得的钥匙的编号
inline int get_key(int key,int num) {
    return key | (1 << num);
}

//返回是否存在门的钥匙
//参数：钥匙集合 门的编号
inline bool has_key(int key,int num) {
    return (key & (1 << num)) > 0;
}


int BFS(int s1,int s2,int v1,int v2) {
    int Min = -1;
    queue<point> Q;
    memset(dis,-1,sizeof(dis));

    Q.push(point(s1,s2,0));
    dis[s1][s2][0] = 0;


    while(!Q.empty()) {
        int x = Q.front().x;
        int y = Q.front().y;
        int key = Q.front().key;
        Q.pop();

        REP(4) {
            int xx = x + delta[o];
            int yy = y + delta[3 - o];
            int kk = key;

            //非法访问
            if(xx < 0 || xx >= n || yy < 0 || yy >= m)
                continue;
            //墙
            if(Map[xx][yy] == '*')
                continue;
            //钥匙
            if(Map[xx][yy] >= 'a' && Map[xx][yy] <= 'j')
                kk = get_key(kk,Map[xx][yy] - 'a');
            //门
            if(Map[xx][yy] >= 'A' && Map[xx][yy] <= 'J')
                if(!has_key(kk,Map[xx][yy] - 'A'))
                    continue;

            //更新节点
            if(dis[xx][yy][kk] == -1) {
                dis[xx][yy][kk] = dis[x][y][key] + 1;
                //剪枝：如果已超过时间，就不再考虑
                if(dis[xx][yy][kk] >= t)
                    continue;
                if(xx == v1 && yy == v2) {
                    Min = ((Min == -1) ? dis[xx][yy][kk] : min(Min,dis[xx][yy][kk]));
                    continue;
                }
                Q.push(point(xx,yy,kk));
            }

        }
    }

    return Min;
}

bool Do() {
    if(scanf("%d%d%d",&n,&m,&t) == EOF)
        return false;

    int s1,s2,v1,v2;
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++) {
            scanf("\n%c",&Map[i][j]);
            if(Map[i][j] == '@') {
                s1 = i;
                s2 = j;
            }
            if(Map[i][j] == '^') {
                v1 = i;
                v2 = j;
            }
        }

    printf("%d\n",BFS(s1,s2,v1,v2));

    return true;
}

int main() {
    while(Do());
    return 0;
}