COJ 拯救瑞恩

试题描述

在n行n列的字符方阵中I表示“我”最初所在位置，R是大兵瑞恩所在位置。4<n<11。 “我”从当前位置可以向上、或下、或左、或右移动一格，只要新点无障碍且未出界。 标有“.”的位置可以通过，标有“*”的位置是障碍物，不能到达和通过。 标有字母A~G的位置代表“门”，是有条件的障碍物，1~7依次是A~G的钥匙。 走到某个门时，若已走路径未经过其钥匙，则门视为“*”,若已经过其钥匙则视为“.”。 求“我”到达瑞恩的位置至少要走多少步？若无法到达输出-1。

输入

输入文件SAVE.IN中共n行n列字符，均为题目所述的字符。字符间无空格。

输出

输出文件SAVE.OUT中仅有答案一个整数。

输入示例

6 ...... ...... .I.3.. .**2*. .**1*C .A*R*B

输出示例

27

设状态为（x,y,S）表示当前在（x,y），拥有的钥匙集合为S，BFS即可。

#include<cstdio>

#include<cctype>

#include<queue>

#include<cstring>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define ren for(int i=first[x];i!=-1;i=next[i])

using namespace std;

inline int read() {

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

struct Arr {int x,y,S;};

char A[][];

int n,vis[][][<<],d[][][<<];

const int mx[]={,-,,},my[]={,,,-};

queue<Arr> Q;

void bfs(int x,int y,int S) {

     vis[x][y][S]=;Q.push((Arr){x,y,S});

     while(!Q.empty()) {

         x=Q.front().x;y=Q.front().y;S=Q.front().S;Q.pop();

         rep(dir,,) {

             int x2=x+mx[dir],y2=y+my[dir],S2=S;

             if(x2<||x2>n||y2<||y2>n) continue;

             if(A[x2][y2]=='*') continue;

             if(isdigit(A[x2][y2])&&!(S&(<<(A[x2][y2]-'')))) continue;

             if(isalpha(A[x2][y2])) S2|=(<<(A[x2][y2]-'A'));

             if(!vis[x2][y2][S2]) {

                 vis[x2][y2][S2]=;

                 d[x2][y2][S2]=d[x][y][S]+;

                 Q.push((Arr){x2,y2,S2});

             }

         }

     }

}

int main() {

    int x1,x2,y1,y2;

    n=read();

    rep(i,,n) scanf("%s",A[i]+);

    rep(i,,n) rep(j,,n) {

        if(A[i][j]=='I') x1=i,y1=j,A[i][j]='.';

        if(A[i][j]=='R') x2=i,y2=j,A[i][j]='.';

    }

    bfs(x1,y1,);

    int ans=1e9;

    rep(S,,<<) if(vis[x2][y2][S]) ans=min(ans,d[x2][y2][S]);

    if(ans!=1e9) printf("%d\n",ans);

    else puts("-1");

    return ;

}