与上一道题：HDU1885 - Key Task基本没什么两样
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int maxn = 25;10 int n, m, fail;11 char G[maxn][maxn];12 int vis[maxn][maxn][2000];13 const int dr[] = {-1, 0, 1, 0};14 const int dc[] = { 0, 1, 0,-1};15 16 struct Node17 {18 int r, c, key, step;19 Node(int r = 0, int c = 0, int key = 0, int step = 0):r(r), c(c), key(key), step(step){}20 };21 22 bool isInside(int r, int c)23 {24 if(r > 0 && r <= n && c > 0 && c <= m && G[r][c] != '*')25 return true;26 else27 return false;28 }29 30 void bfs(int rr, int cc)31 {32 queue q;33 memset(vis, 0, sizeof vis);34 Node node(rr, cc, 0, 0);35 q.push(node);36 while(!q.empty()) {37 Node u = q.front();38 q.pop();39 if(G[u.r][u.c] == '^') {40 if(u.step < fail)41 printf("%d\n", u.step);42 else43 printf("-1\n");44 return;45 }46 for(int i = 0; i < 4; i++) {47 Node v(u.r + dr[i], u.c + dc[i], u.key, u.step+1);48 if(isInside(v.r, v.c)) {49 if(islower(G[v.r][v.c])) {50 int k = G[v.r][v.c] - 'a';51 if((v.key & (1 << k)) == 0) {52 v.key += (1 << k);53 }54 if(!vis[v.r][v.c][v.key]) {55 vis[v.r][v.c][v.key] = 1;56 q.push(v);57 }58 }59 else if(isupper(G[v.r][v.c])) {60 int k = G[v.r][v.c] - 'A';61 if(v.key & (1 << k) && !vis[v.r][v.c][v.key]) {62 vis[v.r][v.c][v.key] = 1;63 q.push(v);64 }65 }66 else {67 if(!vis[v.r][v.c][v.key]) {68 vis[v.r][v.c][v.key] = 1;69 q.push(v);70 }71 }72 }73 }74 }75 printf("-1\n");76 }77 int main()78 {79 // freopen("in.txt", "r", stdin);80 while(scanf("%d %d %d", &n, &m, &fail) != EOF) {81 memset(G, '*', sizeof G);82 int x, y;83 for(int i = 1; i <= n; i++) {84 scanf("%s", G[i]+1);85 G[i][m+1] = '*';86 G[i][m+2] = '\0';87 if(strchr(G[i], '@')) {88 x = i;89 y = strchr(G[i], '@') - *G - i*25;90 }91 }92 //printf("%d %d\n", x, y);93 bfs(x, y);94 }95 return 0;96 }