BFS给力的题目 CSU1259: 跳跳

1259: 跳跳

Time Limit: 1 SecMemory Limit: 128 MB
SUBMIT: 164Solved: 34
[SUBMIT][STATUS]

Description

一个每块地板标记着0~9某个数字的迷宫，其中标记1的地板不可以走，标记2~9的地板可以不花时间地跳到任意相同数字的位置，也可以和标记0的地板一样向前后左右任意方向花1个单位时间移动1的距离。给出起点和终点，求起点到终点的最短时间。

Input

每组数据第一行一个n，表示尺寸，2 <= n <= 100。

接下来n行每行n个0~9的字符，或S表示起点，E表示终点，S和E的运动规则与0相同。整个地图只有一个S和一个E。

Output

每组数据输出一个数，占一行，表示起点到终点可以花费的最短时间。

如果无法到达重点，输出"Oh No!"

Sample Input

5
0S100
00131
00300
00000
003E0
3
S12
010
10E

Sample Output

4
Oh No!

/*比赛的时候不知道脑子怎么了 犯浑 哎 痛失积分啊 比赛结束 回去一小搞 就过了 好可伶 又感觉好差劲啊自己 哎 看着自己的名次 真的有点心痛 感觉付出那么多 怎么就那么点收获 哎 还是把抱怨的时间放在看代码上吧 加油！！！ 付出总会有回报 从小学到高中 一直被验证 我相信这句话以后也会被一次次的验证 我会努力的 今天我败了 明天我会更有劲头 我就不信没有我出头的一天 加油！！！*/
/*一开始思路也有点小问题 应该是遇到2-9的数字就全部push 相应数字 而不是先把它入队 下次碰到再入 */#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int n,s_x,s_y,e_x,e_y;
char map[1200][1200];
int used[1200][1200];
struct haha
{
int x;
int y;
int time;
friend bool operator<(struct haha a,struct haha b)
{
return a.time>b.time;
}
}q,temp;
struct xixi
{
int x[10000];
int y[10000];
int cnt;
}p[20];
int step[4][2]={1,0,-1,0,0,1,0,-1};
int BFS()
{
int i,j,xx,yy,x,y,cnt,count=0,ans=999999999;
priority_queue<haha>que;
while(!que.empty()) que.pop();
memset(used,0,sizeof(used));
q.x=s_x;
q.y=s_y;
q.time=0;
used[s_x][s_y]=0;
que.push(q);
while(!que.empty())
{
temp=que.top();
que.pop();
if(temp.x==e_x&&temp.y==e_y) return ans=temp.time;
for(i=0;i<4;i++)
{
xx=temp.x+step[i][0];
yy=temp.y+step[i][1];
if(xx>=0&&xx<n&&yy>=0&&yy<n&&map[xx][yy]!='1'&&!used[xx][yy])
{
if(map[xx][yy]>='2'&&map[xx][yy]<='9')
{
cnt=p[map[xx][yy]-'0'].cnt;
for(j=0;j<cnt;j++)
{
x=p[map[xx][yy]-'0'].x[j];
y=p[map[xx][yy]-'0'].y[j];
if(!used[x][y])
{
used[x][y]=1;
q.x=x;
q.y=y;
q.time=temp.time+1;
que.push(q);
}
}
}

if(!used[xx][yy])
{
used[xx][yy]=1;
q.x=xx;
q.y=yy;
q.time=temp.time+1;
que.push(q);

}
}
}
}
return ans;
}
int main()
{
int i,j,ans;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<11;i++) p[i].cnt=0;
for(i=0;i<n;i++)
{
scanf("%s",map[i]);
for(j=0;j<n;j++)
{
if(map[i][j]=='S') {s_x=i;s_y=j;}
else if(map[i][j]=='E') {e_x=i;e_y=j;}
else if(map[i][j]<='9'&&map[i][j]>='2')
{
p[map[i][j]-'0'].x[p[map[i][j]-'0'].cnt]=i;
p[map[i][j]-'0'].y[p[map[i][j]-'0'].cnt]=j;
p[map[i][j]-'0'].cnt++;
}
}
}
ans=BFS();
if(ans==999999999) printf("Oh No!\n");
else printf("%d\n",ans);
}
return 0;
}