id="code_img_closed_e96441b6-259f-4616-b114-f009f59f29d1" class="code_img_closed"
class="code_img_opened" Onclick="cnblogs_code_hide(‘e96441b6-259f-4616-b114-f009f59f29d1‘,event)"
#include
#include
#include <string.h>
#include
#include
using namespace std;
const int N=60;
char Map[N][N];
int a[N][N][6],vis[N][N][35];
int dir[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
int n,m,sx,sy,ex,ey;
struct node
{
int x,y,hp,state;
friend bool operator < (node a,node b)
{
return b.hp //在这跪了n遍。。要想优先队列里的值从小到大排列,则比较函数应该从大到小排
}
};
bool in(int x,int y)
{
if (x >= 1&&x <= n&&y >= 1&&y <= m)
return true;
return false;
}
bool judge(int x1,int y1,int x2,int y2,int c)
{
if(abs(x1-x2)+abs(y1-y2) <= c)
return true;
return false;
}
void deal(int x,int y,char ch)
{
if (ch==‘A‘)
{
for (int i = x-2; i <= x+2; i++)
{
for (int j = y-2; j <= y+2; j++)
{
if(in(i,j)&&judge(x,y,i,j,2))
a[i][j][0] = 1;
}
}
}
else if (ch==‘B‘)
{
for (int i = x-3; i <= x+3; i++)
{
for (int j = y-3; j <= y+3; j++)
{
if (in(i,j)&&judge(x,y,i,j,3))
a[i][j][1] = 2;
}
}
}
else if (ch==‘C‘)
a[x][y][2] = 3;
else if (ch==‘D‘)
{
for (int i = x-2; i <= x+2; i++)
{
for (int j = y-2; j <= y+2; j++)
{
if (in(i,j)&&judge(x,y,i,j,2))
a[i][j][3] = 4;
}
}
}
else if (ch==‘E‘)
{
for (int i = x-1; i <= x+1; i ++)
{
for (int j = y-1; j <= y+1; j ++)
{
if (in(i,j)&&judge(x,y,i,j,1))
a[i][j][4] = 5;
}
}
}
}
int bfs()
{
priority_queueq;
while(!q.empty()) q.pop();
q.push((struct node)
{
sx,sy,0,0
});
vis[sx][sy][0] = 1;
while(!q.empty())
{
node temp,t = q.top();
q.pop();
printf("%d %d %d\n",t.x,t.y,t.hp);
if (t.x==ex&&t.y==ey)
return t.hp;
for (int i = 0; i <4; i++)
{
temp.x = t.x+dir[i][0];
temp.y = t.y+dir[i][1];
temp.hp = t.hp;
temp.state = t.state;
if (in(temp.x,temp.y)&&(Map[temp.x][temp.y]==‘C‘||Map[temp.x][temp.y]==‘$‘||Map[temp.x][temp.y]==‘.‘||Map[temp.x][temp.y]==‘!‘))
{
for (int k = 0; k <5; k++)
{
if((temp.state&(1<0&&a[temp.x][temp.y][k])
{
temp.hp+=a[temp.x][temp.y][k];
temp.state+=(1<<k);
}
}
if (!vis[temp.x][temp.y][temp.state])
{
vis[temp.x][temp.y][temp.state] = 1;
q.push(temp);
}
}
}
}
return -1;
}
int main()
{
int t,o = 0;
cin>>t;
while((t--))
{
o++;
cin>>n>>m;
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin>>Map[i][j];
if (Map[i][j]==‘A‘||Map[i][j]==‘B‘||Map[i][j]==‘C‘||Map[i][j]==‘D‘||Map[i][j]==‘E‘)
deal(i,j,Map[i][j]);
if (Map[i][j]==‘$‘)
{
sx = i;
sy = j;
}
if (Map[i][j]==‘!‘)
{
ex = i;
ey = j;
}
}
}
int ans = bfs();
printf("Case %d: %d\n",o,ans);
}
return 0;
}