2011-04-19 21:25:11
题目地址：http://acm.fzu.edu.cn/problem.php?pid=1684
假设楚留香走到map[i][j]点时所剩下的内功为e[i][j],当下一次在从不同路径走到该点时，如果所剩内功大于e[i][j],可以把该路径加入队列中，如果小于或等于，则不加入队列！（第一次做，没有考虑这一点，MLE了！！！！！）
题目说了楚留香消耗的内功为当前一步的墙的高度与其下一步的墙的高度的绝对差，就因为题意没搞清楚，贡献了好多WA~(>_<)~
#include<iostream>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
struct Point
{
int x,y,e,s;
}temp1,temp2;
int a[][2]={{1,0},{-1,0},{0,1},{0,-1}};
int main()
{
char cmap[22][22];
int i,j,r,w,cx,cy,ce,sx,sy,x,y,e,s,map[22][22],ee[22][22];// ee[22][22]数组用来记录当前从不同路径走到该点所剩内功的最多的值
while (scanf("%d%d",&r,&w)!=EOF)
{
queue<Point> qp;
scanf("%d%d%d",&ce,&cx,&cy);
scanf("%d%d",&sx,&sy);
cx++;cy++;sx++;sy++;
memset(map,0,sizeof(map));
for(i=0;i<r+2;i++)
for(j=0;j<w+2;j++)
ee[i][j]=-1;
for(i=1;i<r+1;i++)
scanf("%s",cmap[i]+1);
for(i=0;i<r+2;i++)
{
map[i][0]=-2;
map[i][w+1]=-2;
}
for(j=0;j<w+2;j++)
{
map[0][j]=-2;
map[r+1][j]=-2;
}
temp1.x=cx; temp1.y=cy; temp1.e=ce; temp1.s=0;
ee[cx][cy]=ce;
qp.push(temp1);
while (!qp.empty())
{
temp1=qp.front(); qp.pop();
if(temp1.x==sx&&temp1.y==sy) break;
s=temp1.s+1;
for(i=0;i<4;i++)
{
x=temp1.x+a[i][0]; y=temp1.y+a[i][1];
if(map[x][y]>-2)
{
e=temp1.e-abs(cmap[x][y]-cmap[temp1.x][temp1.y]);
if(e>ee[x][y])
{
ee[x][y]=e;
temp2.x=x; temp2.y=y;
temp2.e=e; temp2.s=s;
qp.push(temp2);
}
}
}
}
if(temp1.x==sx&&temp1.y==sy)
{
printf("%d/n",temp1.s);
}
else
{
printf("UNLUCKY!/n");
}
}
return 0;
}
