BZOJ 1698 [Usaco2007 Feb]Lilypad Pond 荷叶池塘 BFS+最短路_荷叶池塘(lilypad.pas/cpp)-程序员宅基地

技术标签: BZOJ刷题录  c语言  x  bfs  

题意:链接

**方法:**BFS+最短路

解析:

这道题还是挺有意思的。

第一个想法被卡,第一发是二分+bfs,但是这样的话,会有什么处理不了呢?到一个点的流量。

所以就得换想法。

不妨重新定义最短路。

把图中所有的0的点看做可行点,每一次搜出从该点可以到打的0点,然后将这个边权视作1。

即f[i][j]代表到i,j这点的最短路。

显然终点特判;

然后同时记录一下最短路的数量即可。

代码:

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 35
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m;
int map[N][N];
ll num[N][N];
int f[N][N];
int v[N][N];
struct point
{
    int x,y;
}st,ed;
bool canarrive[N][N][N][N];
int xx[9]={
   0,-1,-2,-2,-1,1,2,2,1};
int yy[9]={
   0,-2,-1,1,2,2,1,-1,-2};
void floodfill(int x,int y)
{
    memset(v,0,sizeof(v));
    queue<point>q;
    point tmp;
    tmp.x=x,tmp.y=y;
    q.push(tmp);
    while(!q.empty())
    {
        point u=q.front();
        q.pop();
        for(int i=1;i<=8;i++)
        {
            tmp.x=u.x+xx[i],tmp.y=u.y+yy[i];
            if(tmp.x<=0||tmp.y<=0||tmp.x>n||tmp.y>m||v[tmp.x][tmp.y])continue;
            if(!map[tmp.x][tmp.y]||(tmp.x==ed.x&&tmp.y==ed.y))
            {
                canarrive[x][y][tmp.x][tmp.y]=1;
            }else if(map[tmp.x][tmp.y]==1)
            {
                q.push(tmp);
                v[tmp.x][tmp.y]=1;
            }
        }
    }
}
void bfs()
{
    memset(v,0,sizeof(v));
    queue<point>q;
    q.push(st);
    v[st.x][st.y]=1;
    f[st.x][st.y]=0;
    num[st.x][st.y]=1;
    while(!q.empty())
    {
        point u=q.front();
        q.pop();
        v[u.x][u.y]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(canarrive[u.x][u.y][i][j])
                {
                    if(i==ed.x&&j==ed.y)
                    {
                        if(f[u.x][u.y]<f[i][j])
                        {
                            f[i][j]=f[u.x][u.y];
                            num[i][j]=num[u.x][u.y];
                        }else if(f[u.x][u.y]==f[i][j])
                        {
                            num[i][j]+=num[u.x][u.y];
                        }
                    }else
                    {
                        if(f[u.x][u.y]+1<f[i][j])
                        {
                            f[i][j]=f[u.x][u.y]+1;
                            num[i][j]=num[u.x][u.y];
                            if(!v[i][j])
                            {
                                v[i][j]=1;
                                point tmp;
                                tmp.x=i,tmp.y=j;
                                q.push(tmp);
                            }
                        }else if(f[u.x][u.y]+1==f[i][j])
                        {
                            num[i][j]+=num[u.x][u.y];
                            if(!v[i][j])
                            {
                                v[i][j]=1;
                                point tmp;
                                tmp.x=i,tmp.y=j;
                                q.push(tmp);
                            }
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&map[i][j]);
            if(map[i][j]==3)st.x=i,st.y=j;
            else if(map[i][j]==4)ed.x=i,ed.y=j;
        }
    }
    floodfill(st.x,st.y);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!map[i][j])floodfill(i,j);
        }
    }
    memset(f,0x3f,sizeof(f));
    bfs();
    if(f[ed.x][ed.y]==0x3f3f3f3f)printf("-1\n");
    else
    {   
        printf("%d\n",f[ed.x][ed.y]);
        printf("%lld\n",num[ed.x][ed.y]);
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wzq_QwQ/article/details/47760719

智能推荐

Flink实战3-数据实时写入HBase的Sink方式_flink sink hbase-程序员宅基地

文章浏览阅读5.4k次,点赞3次,收藏26次。背景接入Kafka实时数据经过数据处理写入HBase,后续会应用于类似变量系统以及实时日志中,对于变量系统这类中间需要做实时缓存宽表可能使用HBase连接极其频繁,所以是使用客户端还是Sink的方式就看实际情况而定,具体数据处理后的落库Sink还是比较方便的;摘要关键字Flink,Sink,HBase,数据处理,数据流转设计使用的是Max Well数据源,将业务数据接入Kafka,Flink-Source接入Kafka,中间经过数据流转将数据存储到HBase作实时表;实现说明_flink sink hbase

动态改变title标题_dash 标题-程序员宅基地

文章浏览阅读276次。文章目录动态改变title标题实现效果该上代码了动态改变title标题1、主要用到Vue的自定义指令directive。参考地址: link.实现效果该上代码了一、在main.js引入 // 动态改变title标题 Vue.directive('title', { inserted: function(el, binding) { document.title = binding.value; }, });二、将v-title放在每个文件的根节_dash 标题

使用组件化开发思路替换 SAP Spartacus 的 Logo_替换sap的思路-程序员宅基地

文章浏览阅读299次。简单来说,组件是应用程序的任何部分,可以在逻辑上分组并被视为单一元素,理想情况下可以作为应用程序其余部分的构建块重用。这个组件中可能有其他组件,也可能在其他组件中使用,但每个单独的“组件”都是一个独立的东西。例如,您可能有一个在每个页面上都有 logo 的网站。因此,您可以创建一个“标题组件”,然后您可以为每个页面重用该标题组件,而不是从头开始编写代码。这个标题组件可能包含一个“搜索栏组件”和一个“导航栏”组件,它们是它们自己的独立元素,它们在标题中使用,但也可以在站点的其他地方重用。看个具体的例子:我_替换sap的思路

python界面登录-验证码(三)_pythonui自动化登录验证码-程序员宅基地

文章浏览阅读1.5k次。真的要好好学一下写作了,等好好的有条理的整理自己做过的工作才能方便的进行下一步的使用,能整理好自己的学习的东西才能提高效率,更加明确的进行下一步的工作提高自己的工作效率!!!下一步就是在以下前提下进行网页的登录和课程的查询了:import osimport timefrom bs4 import BeautifulSoup from selenium import webdriv..._pythonui自动化登录验证码

opencv3.1(python3.5)安装_python3.5 opencv-python==3.1.0.0-程序员宅基地

文章浏览阅读7.6k次。1. python管网下载 安装python3.5 (32bit或者64bit)2. 下载 opencv3.1 ( 32bit 或者64bit )opencv_python-3.1.0-cp35-cp35m-win32.whlopencv_python-3.1.0-cp35-cp35m-win_amd64.whl下载链接为:这个链接有多个python的库 numpy_python3.5 opencv-python==3.1.0.0

spring 与hibernate多数据源配置-程序员宅基地

文章浏览阅读89次。Spring2.0.1以后的版本已经支持配置多数据源,并且可以在运行的时候动态加载不同的数据源。通过继承AbstractRoutingDataSource就可以实现多数据源的动态转换。目前做的项目就是需要访问12个数据源,每个数据源的表结构都是相同的,所以要求数据源的变动对于编码人员来说是透明,也就是说同样SQL语句在不同的环境下操作的数据库是不一样的。具体的配置如下:一、首先需要写一个静..._hibernate设置多数据源 parentdatasource

随便推点

自定义CollectionViewCell之-----瀑布流效果_cellcollectionview瀑布流-程序员宅基地

文章浏览阅读1.1k次。本文详细的书写了如何达到瀑布流效果(附图片)_cellcollectionview瀑布流

分布式事务之基础理论(CAP/BASE理论)篇_分布式事务基础理论cap-程序员宅基地

文章浏览阅读346次。一、概述通过前面的学习,我们了解到了分布式事务的基础概念。与本地事务不同的是,分布式系统之所以叫分布式,是因为提供服务的各个节点分布在不同机器上,相互之间通过网络交互。不能因为有一点网络问题就导致整个系统无法提供服务,网络因素成为了分布式事务的考量标准之一。因此,分布式事务需要更进一步的理论支持,接下来,我们先来学习一下分布式事务的CAP理论。在讲解分布式事务控制解决方案之前需要先学习一些基础理论,通过理论知识指导我们确定分布式事务控制的目标,从而帮助我们理解每个解决方案。二、CAP理论CAP是_分布式事务基础理论cap

小程序实现点击按钮回到顶部_微信小程序 topreturnbtn-程序员宅基地

文章浏览阅读526次。按钮样式wxml<view class="topbtn" bindtap="gotopAction" wx:if="{{up_show}}"> <image src="./../../image/topimg.png"></image></view>wxss.topbtn{ position: fixed; width: 120rpx; height: 120rpx; border-radius: 50%; bottom:._微信小程序 topreturnbtn

docker-compose运行ElasticSearch、Kibana、Cerebro_docker-compose elasticsarch kib-程序员宅基地

文章浏览阅读1.1k次。docker-compose.yamlversion: '2.2'services: cerebro: image: lmenezes/cerebro:0.8.4 container_name: cerebro ports: - "9000:9000" command: - -Dhosts.0.host=http://elasticsearch:9200 networks: - es7net kibana: _docker-compose elasticsarch kib

一篇文章快速搞定——deepin搭建java开发环境_deepin jdk-程序员宅基地

文章浏览阅读4.8k次,点赞5次,收藏16次。linux发行版---深度deepin操作系统搭建java开发环境,deepin从入门到放弃系列_deepin jdk

PASCAL VOC 数据集转化为yolo数据集格式_pascalvoc转换成yolov c#-程序员宅基地

文章浏览阅读6.3k次,点赞16次,收藏39次。常常我们拿到的数据集格式是PASCAL VOC的,当我们要用yolo系列的检测算法时,就要将VOC的数据格式转化为yolo所需要的格式。小编就给大家展示转化的过程。_pascalvoc转换成yolov c#

推荐文章

热门文章

相关标签