#include<iostream>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
char a[15][30];
bool b[15][30];
int sx,sy,tx,ty;
int ix[4]={0,0,1,-1};
int iy[4]={1,-1,0,0};
struct Node
{
int x,y;
int days;
};
class cmp
{
public:
bool operator ()(const Node & a, const Node & b)
{
return a.days>b.days; //СµÄÏÈpop()³öÀ´£¬Í¬Àí¿ÉÒÔ¶¨ÒåÓÅÏÈ´óµÄ¶ÓÁÐ
}
};
priority_queue<Node,vector<Node>,cmp> qu;
int bfs()
{
int cx,cy;
int tex,tey;
int steps;
Node node;
node.x=sx,node.y=sy,node.days=0;
while(!qu.empty()) qu.pop();
qu.push(node);
while(!qu.empty())
{
node=qu.top();
qu.pop();
steps=node.days;
cx=node.x;
cy=node.y;
for(int i=0;i<4;i++)
{
tex=cx+ix[i];
tey=cy+iy[i];
if(tex>=0 && tex<15 && tey>=0 && tey<30 && b[tex][tey]==false&& a[tex][tey]!='#')
{
node.x=tex;
node.y=tey;
if(a[tex][tey]=='.')
node.days=steps+1;
else if(a[tex][tey]=='M')
node.days=steps+2;
else if(a[tex][tey]='T')
return steps+1;
b[tex][tey]=true;
qu.push(node);
}
}
}
}
int main()
{
// freopen("s.txt","r",stdin);
//freopen("key.txt","w",stdout);
int ca,i,j;
scanf("%d",&ca);
getchar();
while(ca--)
{
memset(b,0,sizeof(b));
for(i=0;i<15;i++)
{
for(j=0;j<30;j++)
{
scanf("%c",&a[i][j]);
if(a[i][j]=='S')
sx=i,sy=j;
else if(a[i][j]=='T')
tx=i,ty=j;
}
getchar();
}
b[sx][sy]=1;
printf("%d\n",bfs());
}
return 0;
}
啟發：定義變量時最好能賦予實際的意義?。?br> 好的習慣，若是關鍵字可換為大寫字母變量
調試一步一步的！肯定是有問題的一步步來
posted on 2009-05-14 21:49
luis 閱讀(502)
評論(0) 編輯 收藏 引用 所屬分類:
搜索