非常惡心的BFS
#include <iostream>
#include <map>
using namespace std;
map <string , int> h;
int state_count;
int move[4][2] = {{-1 , 0},{1 , 0},{0 , -1},{0 , 1}};
int w, d, ii, ij;
char a[31][31], ss[7], tt[7];
bool jud[31][31][49][7];
struct node
{
int x, y, s, c;
char st[7];
}que[1000001];
char hash(char ch)
{
if(ch == 'r') return '1';
if(ch == 'c') return '2';
if(ch == 'g') return '3';
if(ch == 'm') return '4';
if(ch == 'b') return '5';
if(ch == 'y') return '6';
else return '0';
}
void swap_flag(char ch[7])
{
h[ch] = ++state_count;
swap(ch[4], ch[5]); h[ch] = ++state_count; swap(ch[4], ch[5]);
swap(ch[2], ch[3]); h[ch] = ++state_count; swap(ch[2], ch[3]);
swap(ch[0], ch[1]); h[ch] = ++state_count; swap(ch[0], ch[1]);
swap(ch[4], ch[5]); swap(ch[2], ch[3]);
h[ch] = ++state_count;
swap(ch[4], ch[5]); swap(ch[2], ch[3]);
swap(ch[4], ch[5]); swap(ch[0], ch[1]);
h[ch] = ++state_count;
swap(ch[4], ch[5]); swap(ch[0], ch[1]);
swap(ch[0], ch[1]); swap(ch[2], ch[3]);
h[ch] = ++state_count;
swap(ch[0], ch[1]); swap(ch[2], ch[3]);
swap(ch[0], ch[1]); swap(ch[2], ch[3]); swap(ch[4], ch[5]);
h[ch] = ++state_count;
swap(ch[0], ch[1]); swap(ch[2], ch[3]); swap(ch[4], ch[5]);
}
void bulid_state()
{
char ch[7] = "123456", temp;
h.clear();
state_count = 0;
int i, j, cnt = 1;
swap_flag(ch);
for(i = 2; i <= 6; i ++)
{
if(cnt == 3 ) cnt = 1;
if(cnt == 1)
{
swap(ch[5], ch[3]); swap(ch[4], ch[2]);
swap_flag(ch);
cnt ++;
}
else if(cnt == 2)
{
swap(ch[3], ch[1]); swap(ch[2], ch[0]);
swap_flag(ch);
cnt ++;
}
}
}
void find()
{
int i, j;
for(i = 0; i < d; i ++)
for(j = 0; j < w; j ++)
if(a[i][j] == '#')
{
ii = i;
ij = j;
a[i][j] = 'w';
return;
}
}
void changed(char ch[7], int i)
{
if(i == 0)
{
tt[0] = ch[3]; tt[1] = ch[2]; tt[2] = ch[0];
tt[3] = ch[1]; tt[4] = ch[4]; tt[5] = ch[5];
}
if(i == 1)
{
tt[0] = ch[2]; tt[1] = ch[3]; tt[2] = ch[1];
tt[3] = ch[0]; tt[4] = ch[4]; tt[5] = ch[5];
}
if(i == 2)
{
tt[0] = ch[4]; tt[1] = ch[5]; tt[2] = ch[2];
tt[3] = ch[3]; tt[4] = ch[1]; tt[5] = ch[0];
}
if(i == 3)
{
tt[0] = ch[5]; tt[1] = ch[4]; tt[2] = ch[2];
tt[3] = ch[3]; tt[4] = ch[0]; tt[5] = ch[1];
}
tt[6] = '\0';
}
bool check(node t)
{
if(t.x < 0 || t.y < 0 || t.x >=d || t.y >= w || jud[t.x][t.y][h[t.st]][t.c] == 1 || a[t.x][t.y] == 'k')
return false;
if(a[t.x][t.y] != 'w' && a[t.x][t.y] != 'k' && hash(a[t.x][t.y]) != t.st[0])
return false;
if(a[t.x][t.y] != 'w' && a[t.x][t.y] != 'k' && hash(a[t.x][t.y]) == t.st[0] && t.st[0] != hash(ss[t.c]))
return false;
return true;
}
int bfs()
{
int close = -1, open = 0, i, j;
node tp, next;
memset(jud, 0, sizeof(jud));
que[0].x = ii;
que[0].y = ij;
que[0].s = 0;
que[0].c = 0;
strcpy(que[0].st , "123456");
jud[ii][ij][h[que[0].st]][0] = 1;
while(close < open)
{
close ++;
tp = que[close];
//printf("%d %d %s %d\n",tp.x,tp.y,tp.st,tp.c);
for(i = 0; i < 4; i ++)
{
next.x = tp.x + move[i][0];
next.y = tp.y + move[i][1];
next.s = tp.s + 1;
next.c = tp.c;
changed(tp.st , i);
strcpy( next.st , tt );
//printf("%d %d %s %s %d %c\n",next.x,next.y,next.st,ss, next.c,a[next.x][next.y]);
if(check(next) == false) continue;
if(hash(a[next.x][next.y]) == next.st[0] && next.st[0] == hash(ss[next.c]))
next.c ++;
if(next.c == 6) return next.s;
open ++;
que[open] = next;
jud[next.x][next.y][h[next.st]][next.c] = 1;
}
}
return -1;
}
int main()
{
int step;
bulid_state();
while(scanf("%d %d",&w, &d), w+d)
{
int i;
for(i = 0; i < d; i ++) scanf("%s",a[i]);
scanf("%s",ss);
find();
step = bfs();
if(step > 0) printf("%d\n", step);
else puts("unreachable");
}
}
/*
7 4
#ycbrkk
kkkkgkk
kkkkwkk
kkkkmkk
ycbrgm
*/