BZOJ 1294 [SCOI2009]围豆豆Bean

2023-10-09 04:38
文章标签 bean bzoj 1294 scoi2009 豆豆

本文主要是介绍BZOJ 1294 [SCOI2009]围豆豆Bean,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

Input

第一行两个整数N和M,为矩阵的边长。第二行一个整数D,为豆子的总个数。第三行包含D个整数V1到VD,分别为每颗豆子的分值。接着N行有一个N×M的字符矩阵来描述游戏矩阵状态,0表示空格,#表示障碍物。而数字1到9分别表示对应编号的豆子。

Output

仅包含一个整数,为最高可能获得的分值。

Sample Input

3 8
3
30 -100 30
00000000
010203#0
00000000

Sample Output

38

HINT

50%的数据满足1≤D≤3。

100%的数据满足1≤D≤9,1≤N, M≤10,-10000≤Vi≤10000。


这个题呀,好题。

可以边搜索边更新状态,用射线法(自己百度吧)。


#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,d,ans,v[11],mp[11][11],x[11],y[11],dis[1105][11][11];
bool inq[1105][11][11];
int xx[]={-1,0,1,0},yy[]={0,-1,0,1};
struct node
{int x,y,z;//x,y坐标,z吃豆子的情况 
};
queue<node>q;
void bfs(int sx,int sy)
{memset(dis,0x3f,sizeof(dis));memset(inq,0,sizeof(inq));node t;dis[0][sx][sy]=0;t.x=sx,t.y=sy,t.z=0;q.push(t);inq[0][sx][sy]=1;while(!q.empty()){node u=q.front();q.pop();inq[u.z][u.x][u.y]=0;for(int i=0;i<=3;i++)if(u.x+xx[i]>=1&&u.x+xx[i]<=n&&u.y+yy[i]>=1&&u.y+yy[i]<=m&&mp[u.x+xx[i]][u.y+yy[i]]==0){t.x=u.x+xx[i],t.y=u.y+yy[i],t.z=u.z;for(int j=1;j<=d;j++)if(t.y>y[j]&&((u.x>x[j]&&t.x<=x[j])||(u.x<=x[j]&&t.x>x[j])))//垂直于x轴的射线 t.z^=(1<<(j-1));if(dis[t.z][t.x][t.y]>dis[u.z][u.x][u.y]+1){dis[t.z][t.x][t.y]=dis[u.z][u.x][u.y]+1;if(!inq[t.z][t.x][t.y]){inq[t.z][t.x][t.y]=1;q.push(t);}}}}int end=(1<<d)-1;for(int i=1;i<=end;i++){int tmp=-dis[i][sx][sy];for(int j=1;j<=d;j++)if(i&(1<<(j-1)))tmp+=v[j];ans=max(tmp,ans);}
}
int main()
{scanf("%d%d%d",&n,&m,&d);for(int i=1;i<=d;i++)scanf("%d",&v[i]);for(int i=1;i<=n;i++){char s[15];scanf("%s",s+1);for(int j=1;j<=m;j++)if(s[j]=='#')mp[i][j]=1;else if(s[j]=='0')mp[i][j]=0;else{mp[i][j]=1;x[s[j]-'0']=i;y[s[j]-'0']=j;}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]==0)bfs(i,j);printf("%d\n",ans);return 0;
}


这篇关于BZOJ 1294 [SCOI2009]围豆豆Bean的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/170392

相关文章

Spring 中使用反射创建 Bean 实例的几种方式

《Spring中使用反射创建Bean实例的几种方式》文章介绍了在Spring框架中如何使用反射来创建Bean实例,包括使用Class.newInstance()、Constructor.newI... 目录1. 使用 Class.newInstance() (仅限无参构造函数):2. 使用 Construc

Springboot控制反转与Bean对象的方法

《Springboot控制反转与Bean对象的方法》文章介绍了SpringBoot中的控制反转(IoC)概念,描述了IoC容器如何管理Bean的生命周期和依赖关系,它详细讲解了Bean的注册过程,包括... 目录1 控制反转1.1 什么是控制反转1.2 SpringBoot中的控制反转2 Ioc容器对Bea

在 Spring Boot 中使用 @Autowired和 @Bean注解的示例详解

《在SpringBoot中使用@Autowired和@Bean注解的示例详解》本文通过一个示例演示了如何在SpringBoot中使用@Autowired和@Bean注解进行依赖注入和Bean... 目录在 Spring Boot 中使用 @Autowired 和 @Bean 注解示例背景1. 定义 Stud

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

在Java中使用ModelMapper简化Shapefile属性转JavaBean实战过程

《在Java中使用ModelMapper简化Shapefile属性转JavaBean实战过程》本文介绍了在Java中使用ModelMapper库简化Shapefile属性转JavaBean的过程,对比... 目录前言一、原始的处理办法1、使用Set方法来转换2、使用构造方法转换二、基于ModelMapper

解决Spring运行时报错:Consider defining a bean of type ‘xxx.xxx.xxx.Xxx‘ in your configuration

《解决Spring运行时报错:Considerdefiningabeanoftype‘xxx.xxx.xxx.Xxx‘inyourconfiguration》该文章主要讲述了在使用S... 目录问题分析解决方案总结问题Description:Parameter 0 of constructor in x

SpringBoot项目删除Bean或者不加载Bean的问题解决

《SpringBoot项目删除Bean或者不加载Bean的问题解决》文章介绍了在SpringBoot项目中如何使用@ComponentScan注解和自定义过滤器实现不加载某些Bean的方法,本文通过实... 使用@ComponentScan注解中的@ComponentScan.Filter标记不加载。@C

Spring中Bean有关NullPointerException异常的原因分析

《Spring中Bean有关NullPointerException异常的原因分析》在Spring中使用@Autowired注解注入的bean不能在静态上下文中访问,否则会导致NullPointerE... 目录Spring中Bean有关NullPointerException异常的原因问题描述解决方案总结

Spring 源码解读:自定义实现Bean定义的注册与解析

引言 在Spring框架中,Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义,Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制,帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry,以全面掌握Bean注册和解析的核心原理。

读Spring实战(第四版)概括—装配Bean

很久很久以前读过Spring实战(第三版),因为第三版和第四部差异还是特别明显的,在整体思想上有了比较重大的改变,比如用注解和JavaConfig替换Xml以及现在非常火热的Springboot在书的最后也有提到。OK,开始看书,书本的第一章讲了一下Spring存在的目的(简化Java开发)和Spring的功能,以及Spring3->Spring4增加了哪些功能,那我就从第二章开始概括本书,以给我