首页 > 代码库 > bzoj3393 [Usaco2009 Jan]Laserphones 激光通讯
bzoj3393 [Usaco2009 Jan]Laserphones 激光通讯
Description
Input
第1行输入w和H,之后W行H列输入地图,图上符号意义如题目描述.
Output
最少的对角镜数量.
Sample Input
7 8
.......
...... C
......*
*****.*
....*..
....*..
.C ..*..
.......
.......
...... C
......*
*****.*
....*..
....*..
.C ..*..
.......
Sample Output
3
求拐点数最小
直接搜索是不行的,因为可能出现一个点当前被更新的状态并不是它最优的状态
所以像spfa那样允许多次入队,这样虽然慢一点但是没有后效性,而且这么小的数据也不会慢到哪里去吧
#include<cstdio>#include<iostream>#include<cstring>#include<queue>#define LL long long#define inf 598460606#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;struct que{int x,y,dire,dist;}now,wrk;bool operator < (const que &a,const que &b){return a.dist>b.dist;}priority_queue <que> q;const int mx[4]={0,1,0,-1};const int my[4]={1,0,-1,0};int n,m,sx,sy,ex,ey;bool mrk[110][110];int dist[110][110][4];int main(){ scanf("%d%d",&m,&n); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { char ch=getchar(); while (ch!=‘C‘&&ch!=‘.‘&&ch!=‘*‘)ch=getchar(); if (ch==‘*‘)mrk[i][j]=1; if (ch==‘C‘){if (!sx){sx=i;sy=j;}else {ex=i;ey=j;} } } memset(dist,127,sizeof(dist)); now.x=sx;now.y=sy;now.dist=0; for (int i=0;i<4;i++) { now.dire=i; q.push(now); dist[sx][sy][i]=0; } while (!q.empty()) { now=q.top();q.pop(); int k=now.dire; wrk=now; while (wrk.x+mx[k]>=1&&wrk.x+mx[k]<=n&&wrk.y+my[k]>=1&&wrk.y+my[k]<=m&&!mrk[wrk.x+mx[k]][wrk.y+my[k]]&&dist[wrk.x+mx[k]][wrk.y+my[k]][k]>wrk.dist) { wrk.x+=mx[k];wrk.y+=my[k]; dist[wrk.x][wrk.y][k]=dist[now.x][now.y][k]; q.push(wrk); } wrk=now;wrk.dist++; for (int k=0;k<4;k++) if(dist[now.x][now.y][k]>now.dist+1) { dist[now.x][now.y][k]=now.dist+1; wrk.dire=k; q.push(wrk); } } int ans=inf; for (int k=0;k<4;k++) ans=min(ans,dist[ex][ey][k]); printf("%d\n",ans);}
bzoj3393 [Usaco2009 Jan]Laserphones 激光通讯
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。