2534: The Hero Rescued The Princess
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 |
3s | 65536K | 210 | 61 | Standard |
美丽的公主被关在古老的施了咒语的城堡中，你作为当今世上最勇敢的英雄，决定救出这位美丽的公主。
如果你成功了，最后公主就会嫁给你。当然故事有点俗套，至少如果你把她救出了，我会免费送你一个气球。
但是有很多的英雄去救，如果别人在你之前把公主救了，那么公主可就不属于你了。所以你一定要加快行动，现在就向目标进发吧。
这个城堡的地图由一个（15*30）的字符矩阵构成，我们可以保证矩阵是封闭的。
城堡中有很多的小怪，当然这对于武功高强你的一定不成问题，但你你需要比平时多用一天的时间。
字符有：
'#'，表示城堡的墙，你不可以穿过；
'.'，表示空地，你需要花费一天的时间走过。
'M'，表示此地有怪，你需要两天的时间走过。
'S'，表示你的初始地点
'T'，表示公主的所在地
首行会有一个整数n(n<=10),表示后面有多少个迷宫，每个城堡由（15*30) 的矩阵构成，
每个城堡有且仅有一个S和T，现在你需要设计合适的路线保证总是尽量早的到公主的地方。
如果没有路线可以救出公主，输出-1；
你只能向上，向下，向左或向右走，但不可以斜着走。
Sample input
1 ############################## #.S#.........................# #..#.........................# #...MT.......................# #.#..........................# #............................# #............................# #............................# #............................# #............................# #............................# #............................# #............................# #............................# ##############################
Sample output
6
Problem Source: Keenas
#include<stdio.h>
#include<string.h>
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
char map[20][40];
struct node
{
int x,y,l;
}a[1000];
int f[20][40];
int bfs(int x,int y)
{
int i,j,top=0;
a[top].x=x,a[top].y=y;
a[top++].l=0;
for(i=0;i<top;i++)
{
if(map[a[i].x][a[i].y]=='M')
{
a[top].x=a[i].x,a[top].y=a[i].y,a[top++].l=a[i].l+1;map[a[i].x][a[i].y]='.';continue;
}
for(j=0;j<4;j++)
{
int tx=a[i].x+xx[j];
int ty=a[i].y+yy[j];
if(f[tx][ty]==0)
{
a[top].x=tx;a[top].y=ty;
a[top].l=a[i].l+1;
if(map[tx][ty]=='T') return a[top].l;
f[tx][ty]=1;
top++;
}
}
}
return -2;
}
int main()
{
int i,j,n;
scanf("%d",&n);
while(n--)
{
for(i=0;i<15;i++)
scanf("%s",map[i]);
int t,p,q;
memset(f,0,sizeof(f));
for(i=0;i<15;i++) for(j=0;j<50;j++)
{
if(map[i][j]=='#') f[i][j]=1;
if(map[i][j]=='S') p=i,q=j;
}
t=bfs(p,q);
if(t!=-2)
{
printf("%d/n",t);
}
else
printf("-1/n");
}
return 0;
}
/*
2
##############################
#.SM.........................#
#.#M.#.......................#
#..#M.#......................#
#.#..#.......................#
#............................#
#............................#
#............................#
#............................#
#............................#
#............................#
#............................#
#...........................M#
#...........................T#
##############################
##############################
#.S..........................#
#.##.#.......................#
#...M.#......................#
#.#..#.......................#
#............M...............#
#...........M................#
#.........MM..T..............#
#...........M.M..............#
#............................#
#............................#
#............................#
#............................#
#............................#
##############################
*/