【Link】:

【Description】

给你一个n*m的格子;

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

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

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

【Solution】

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

sta用10位的二进制表示;

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

以及获取新的钥匙

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

【NumberOf WA】

1

【Reviw】

【Code】

#include 
     
      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 
      
        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;}