首页 > 代码库 > poj 2312 Battle City(优先队列+bfs)
poj 2312 Battle City(优先队列+bfs)
题目链接:http://poj.org/problem?id=2312
题目大意:给出一个n*m的矩阵,其中Y是起点,T是终点,B和E可以走,S和R不可以走,要注意的是走B需要2分钟,走E需要一分钟。最后求解Y--->T的最短时间!!
看到这题首先想到广搜来找最短时间,但是这里可以对B和E进行处理,方便计算~
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 using namespace std; 6 int dir[4][2]= {1,0,-1,0,0,1,0,-1}; 7 bool vis[310][310]; 8 char map[310][310]; 9 int m,n,sx,sy;10 struct node11 {12 int x,y,time;13 friend bool operator<(node a,node b)14 {15 return a.time>b.time;16 }17 };18 19 int bfs()20 {21 node s,ss,sss;22 priority_queue<node>q;23 s.x=sx;24 s.y=sy;25 s.time=0;26 q.push(s);27 vis[sx][sy]=1;28 while (!q.empty())29 {30 ss=q.top();31 q.pop();32 for (int i=0; i<4; i++)33 {34 sss.x=ss.x+dir[i][0];35 sss.y=ss.y+dir[i][1];36 if (sss.x<0||sss.y<0||sss.x>=n||sss.y>=m||map[sss.x][sss.y]==‘R‘ || map[sss.x][sss.y]==‘S‘||vis[sss.x][sss.y])37 continue;38 if (map[sss.x][sss.y]==‘B‘)39 sss.time=ss.time+2;40 else41 sss.time=ss.time+1;42 //sss.time=ss.time+1;43 if (map[sss.x][sss.y]==‘T‘)44 return sss.time;45 vis[sss.x][sss.y]=1;46 q.push(sss);47 }48 }49 return -1;50 }51 52 int main ()53 {54 while (~scanf("%d%d",&n,&m))55 {56 if (n==0&&m==0)57 break;58 memset(vis,0,sizeof(vis));59 for (int i=0; i<n; i++)60 {61 getchar();62 for (int j=0; j<m; j++)63 {64 scanf("%c",&map[i][j]);65 if (map[i][j]==‘Y‘)66 {67 sx=i;68 sy=j;69 }70 }71 }72 printf ("%d\n",bfs());73 }74 return 0;75 }
还有一种,单纯的广搜也是可以的。
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 using namespace std; 6 int dir[4][2]= {1,0,-1,0,0,1,0,-1}; 7 bool vis[310][310]; 8 char map[310][310]; 9 int m,n,sx,sy;10 struct node11 {12 int x,y,time;13 };14 15 int bfs()16 {17 node s,ss,sss;18 //priority_queue<node>q;19 queue<node>q;20 s.x=sx;21 s.y=sy;22 s.time=0;23 q.push(s);24 vis[sx][sy]=1;25 while (!q.empty())26 {27 ss=q.front();28 q.pop();29 for (int i=0; i<4; i++)30 {31 sss.x=ss.x+dir[i][0];32 sss.y=ss.y+dir[i][1];33 if (sss.x<0||sss.y<0||sss.x>=n||sss.y>=m||map[sss.x][sss.y]==‘R‘ || map[sss.x][sss.y]==‘S‘||vis[sss.x][sss.y])34 continue;35 if (map[sss.x][sss.y]==‘B‘)36 sss.time=ss.time+2;37 else38 sss.time=ss.time+1;39 //sss.time=ss.time+1;40 if (map[sss.x][sss.y]==‘T‘)41 return sss.time;42 vis[sss.x][sss.y]=1;43 q.push(sss);44 }45 }46 return -1;47 }48 49 int main ()50 {51 while (~scanf("%d%d",&n,&m))52 {53 if (n==0&&m==0)54 break;55 memset(vis,0,sizeof(vis));56 for (int i=0; i<n; i++)57 {58 getchar();59 for (int j=0; j<m; j++)60 {61 scanf("%c",&map[i][j]);62 if (map[i][j]==‘Y‘)63 {64 sx=i;65 sy=j;66 }67 }68 }69 printf ("%d\n",bfs());70 }71 return 0;72 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。