状态压缩＋ＢＦＳ ／／记忆话搜索
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
char map[55][55];
int mp[55][55];
int dp[55][55][1<<5];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int xe[5]= {1,2,3,4,5};
struct node
{
int x, y, hp;
} st, u, v;
int abs(int x)
{
if(x < 0) return -x;
return x;
}
queue < node > que;
int main()
{
int T;
int n, m, sx, sy, ex, ey, cas=1;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++)
{
scanf("%s", map[i]);
}
memset(mp, 0, sizeof(mp));//对图上每个点打上类型
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(map[i][j] == '#')
{
mp[i][j] = -1;
continue;
}
if(map[i][j] == '$')
{
sx = i;
sy = j;
continue;
}
if(map[i][j] == '!')
{
ex = i;
ey = j;
continue;
}
if(map[i][j] == 'A')
{
mp[i][j] = -1;//不可以踏入的
for(int x = -2; x < 3; x++)
{
for(int y = -2; y < 3; y++)
{
if(abs(x) + abs(y) > 2) continue;
int bx = i + x;
int by = j + y;
if(bx >= 0 && bx < n && by >= 0 && by < m && mp[bx][by] != -1)
{
mp[bx][by] |= 1;
}
}
}
continue;
}
if(map[i][j] == 'B')
{
mp[i][j] = -1;//不可以踏入的
for(int x = -3; x < 4; x++)
{
for(int y = -3; y < 4; y++)
{
if(abs(x) + abs(y) > 3) continue;
int bx = i + x;
int by = j + y;
if(bx >= 0 && bx < n && by >= 0 && by < m && mp[bx][by] != -1)
{
mp[bx][by] |= 1 << 1;
}
}
}
continue;
}
if(map[i][j] == 'C')
{
mp[i][j] |= 1 << 2;
}
if(map[i][j] == 'D')
{
mp[i][j] = -1;//不可以踏入的
for(int x = -2; x < 3; x++)
{
for(int y = -2; y < 3; y++)
{
if(abs(x) + abs(y) > 2) continue;
int bx = i + x;
int by = j + y;
if(bx >= 0 && bx < n && by >= 0 && by < m && mp[bx][by] != -1)
{
mp[bx][by] |= 1 << 3;
}
}
}
continue;
}
if(map[i][j] == 'E')
{
mp[i][j] = -1;//不可以踏入的
for(int x = -1; x < 2; x++)
{
for(int y = -1; y < 2; y++)
{
if(abs(x) + abs(y) > 1) continue;
int bx = i + x;
int by = j + y;
if(bx >= 0 && bx < n && by >= 0 && by < m && mp[bx][by] != -1)
{
mp[bx][by] |= 1 << 4;
}
}
}
continue;
}
}
}
/*for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
printf("%d ",mp[i][j]);
}
puts("");
}*/
st.x = sx;
st.y = sy;
st.hp = 0;
memset(dp, -1, sizeof(dp));
dp[st.x][st.y][0] = 0;
que.push(st);
int a, b, c;
while(!que.empty())
{
u = que.front();
que.pop();
for(int i = 0; i < 4; i++)
{
b = dp[u.x][u.y][u.hp];
v.x = u.x + dx[i];
v.y = u.y + dy[i];
if(v.x>=n||v.x<0||v.y>=m||v.y<0||mp[v.x][v.y]==-1)continue;
for(int j=0; j<5; j++)
{
a=mp[v.x][v.y]&(1<<j);
c=u.hp&(1<<j);
if(a!=0&&c==0)
{
b+=xe[j];
}
}
v.hp = u.hp | mp[v.x][v.y];
if(dp[v.x][v.y][v.hp]==-1||dp[v.x][v.y][v.hp]>b)
{
dp[v.x][v.y][v.hp]=b;
que.push(v);
}
}
}
int ans=-1;
for(int i=0; i< (1<<5); i++)
{
if(dp[ex][ey][i]!=-1 && (dp[ex][ey][i]<ans ||ans==-1))
{
ans=dp[ex][ey][i];
}
}
printf("Case %d: %d\n",cas++,ans);
}
return 0;
}