【Link】:

【Description】



给你一个n*m的格子;

里面有钥匙,以及钥匙能开的门;

以及墙,以及起点,以及出口;

问你从起点出发,到出口的话,能不能在t时间内到;

【Solution】



dis[x][y][sta]表示到了点(x,y)然后拥有钥匙的状态为sta的最短时间花费;

sta用10位的二进制表示;

根据sta判断能不能接着往下走,以及能不能打开某一扇门;

以及获取新的钥匙

到了终点,就记录f的最小值;



【NumberOf WA】



1



【Reviw】

【Code】

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

const int dx[5] = {0,1,-1,0,0};

const int dy[5] = {-1,0,0,1,0};

const int INF = 0x3f3f3f3f;

struct node{

    int x,y,sta;

};

char s[N+5][N+5];

int a[N+5][N+5],n,m,t,Sx,Sy,Tx,Ty;

int dis[N+5][N+5][1024],two[12];

queue <node> dl;

node temp;

bool bfs(){

    while (!dl.empty()) dl.pop();

    dis[Sx][Sy][0] = 0;

    temp.x = Sx,temp.y = Sy,temp.sta = 0;

    dl.push(temp);

    int mi = INF;

    while (!dl.empty()){

        temp = dl.front();

        dl.pop();

        int x = temp.x, y = temp.y,tsta = temp.sta,sta;

        if (x==Tx && y==Ty) mi = min(mi,dis[x][y][tsta]);

        for (int i = 0; i<= 3;i++){

            int tx = x + dx[i],ty = y + dy[i];

            if (tx<1 || tx > n || ty<1|| ty>m) continue;

            if (a[tx][ty]==0) continue;

            if (a[tx][ty]==100 || (a[tx][ty]>=1 && a[tx][ty]<=10)){

                if (a[tx][ty]!=100)

                    sta = tsta|two[a[tx][ty]-1];

                else

                    sta = tsta;

                if (dis[tx][ty][sta]==-1 || dis[tx][ty][sta]>dis[x][y][tsta]+1){

                    dis[tx][ty][sta] = dis[x][y][tsta]+1;

                    temp.x = tx,temp.y = ty,temp.sta = sta;

                    dl.push(temp);

                }

            }

            if (a[tx][ty]>=11 && a[tx][ty]<=20){

                sta = tsta;

                int temp1 = a[tx][ty]-11;

                if (two[temp1]&sta){

                    if (dis[tx][ty][sta]==-1 || dis[tx][ty][sta]>dis[x][y][tsta]+1){

                        dis[tx][ty][sta] = dis[x][y][tsta]+1;

                        temp.x = tx,temp.y = ty,temp.sta = sta;

                        dl.push(temp);

                    }

                }

            }

        }

    }

    if (mi==INF) return false;

    if (mi>=t) return false;

    printf("%d\n",mi);

    return true;

}

int main(){

    //freopen("F:\\rush.txt","r",stdin);

    two[0] = 1;

    for (int i = 1;i <= 10;i++) two[i] = two[i-1]*2;

    while (~scanf("%d%d%d",&n,&m,&t)){

        memset(dis,255,sizeof dis);

        for (int i = 1;i <= n;i++)

            scanf("%s",s[i]+1);

        for (int i = 1;i <= n;i++)

            for (int j = 1;j <= m;j++){

                if (s[i][j]=='@'){

                    Sx = i,Sy = j;

                    a[i][j] = 100;

                }

                if (s[i][j]>='A' && s[i][j]<='Z'){

                    a[i][j] = s[i][j]-'A'+1+10;

                }

                if (s[i][j]>='a' && s[i][j]<='z'){

                    a[i][j] = s[i][j]-'a'+1;

                }

                if (s[i][j]=='^'){

                    Tx = i,Ty = j;

                    a[i][j] = 100;

                }

                if (s[i][j]=='*'){

                    a[i][j] = 0;

                }

                if (s[i][j]=='.'){

                    a[i][j]=100;

                }

            }

        if (!bfs()) puts("-1");

    }

    return 0;

}