bzoj3393 [Usaco2009 Jan]Laserphones 激光通讯

Description

Input

第1行输入w和H,之后W行H列输入地图,图上符号意义如题目描述.

Output

最少的对角镜数量.

Sample Input

7 8
.......
...... 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.1415926535897932384626433832795028841971
using 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);
}

  

时间: 11-10

bzoj3393 [Usaco2009 Jan]Laserphones 激光通讯的相关文章

bzoj3396[Usaco2009 Jan]Total flow 水流*

bzoj3396[Usaco2009 Jan]Total flow 水流 题意: 求无环图的最大流.边数≤700. 题解: 管它有没有环.注意本题的节点标号既有大写字母,也有小写字母. 代码: 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #de

3396: [Usaco2009 Jan]Total flow 水流

3396: [Usaco2009 Jan]Total flow 水流 Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 179  Solved: 73[Submit][Status] Description Input 第1行输入N,之后N行每行描述一条水管,前两个英文字母表示水管的两端(大小写字母是不一样的),后一个整数表示水管的流量,流量不会超过1000. Output 一个整数,表示总流量. Sample Input 5 A B 3 B C 3

BZOJ3394: [Usaco2009 Jan]Best Spot 最佳牧场

3394: [Usaco2009 Jan]Best Spot 最佳牧场 Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 11  Solved: 9[Submit][Status] Description Input 第1行输入三个整数P,F C.之后F行每行输入一个整数表示一个贝茜喜欢的牧场.之后C行每行输入三个整数ai,bi,Ti,描述一条路. Output 一个整数,满足题目要求的最佳牧场.如果有多个答案,输出编号最小的 Sample Input

bzoj 1574: [Usaco2009 Jan]地震损坏Damage

Description 农夫John的农场遭受了一场地震.有一些牛棚遭到了损坏,但幸运地,所有牛棚间的路经都还能使用. FJ的农场有P(1 <= P <= 30,000)个牛棚,编号1..P. C(1 <= C <= 100,000)条双向路经联接这些牛棚,编号为1..C. 路经i连接牛棚a_i和b_i (1 <= a_i<= P;1 <= b_i <= P).路经可能连接a_i到它自己,两个牛棚之间可能有多条路经.农庄在编号为1的牛棚. N (1 <

BZOJ1576 [Usaco2009 Jan]安全路经Travel

首先用Dijkstra做出最短路生成树,设dis[p]为1到p点的最短路长度 对于一条不在生成树上的边u -> v,不妨设fa为u.v的lca 则一fa到v的路径上的任意点x都可以由u达到,走的方式是1 -> fa -> u -> v -> x,dis'[x] = dis[u] + dis(u, v) + dis[v] - dis[x] 于是可以用dis[u] + dis(u, v) + dis[v]更新fa到v的路径上的所有点 链剖一下,线段树lazytag就好了,连pus

bzoj 1575: [Usaco2009 Jan]气象牛Baric

Description 为了研究农场的气候,Betsy帮助农夫John做了N(1 <= N <= 100)次气压测量并按顺序记录了结果M_1...M_N(1 <= M_i <= 1,000,000). Betsy想找出一部分测量结果来总结整天的气压分布. 她想用K(1 <= K <= N)个数s_j (1 <= s_1 < s_2 < ... < s_K <= N)来概括所有测量结果. 她想限制如下的误差: 对于任何测量结果子集,每一个非此

[BZOJ1575] [Usaco2009 Jan]气象牛Baric(DP)

传送门 DP f[i][j]表示前i个中选j个的最优解 预处理g[i][j]表示选i~j对答案的贡献 那么就可以n^3乱搞了! 注意边界 #include <cstdio> #include <cstring> #include <iostream> #define N 110 #define abs(x) ((x) < 0 ? -(x) : (x)) #define min(x, y) ((x) < (y) ? (x) : (y)) int n, e, a

【BZOJ】1576 [Usaco2009 Jan]安全路经Travel

[算法]最短路树+(树链剖分+线段树)||最短路树+并查集 [题解] 两种方法的思想是一样的,首先题目限制了最短路树唯一. 那么建出最短路树后,就是询问对于每个点断掉父边后重新找路径的最小值,其它路径只能是这个点和其子树节点通过非树边到达非子树节点. 这样考虑很难统计,换个角度考虑每条非树边的影响. 一条非树边连接两个端点u,v,它们会有一个LCA,那么这条非树边就可以影响u~LCA和v~LCA两条链上的点. 这样依然不方便统计,因为两条链上每个点的影响各不相同,所以使用差分的思想. 定义一条非

[BZOJ1574] [Usaco2009 Jan]地震损坏Damage(贪心 + dfs)

传送门 告诉你一些点不能到达1,由于是双向边,也就是1不能到达那些点 那么从1开始dfs,如果当前点能到达不能到达的点,那么当前点就是损坏的. #include <cstdio> #include <cstring> #include <iostream> #define N 100001 int n, m, p, cnt, tot; int head[N], to[N << 1], next[N << 1]; bool vis[N], flag