Description

Input

The first line has two integers N and M, Is the side length of the matrix . The second line is an integer D, Is the total number of beans . The third line contains D It's an integer V1 To VD, The score of each bean . next N Yes, there is one N×M Character matrix to describe the state of the game matrix ,0 Said the blank space ,# It means an obstacle . And the number 1 To 9 They represent the corresponding number of beans .

Output

Contains only one integer , For the highest possible score .

Sample Input

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

Sample Output

38

HINT

50% Data of 1≤D≤3.
100% Data of 1≤D≤9,1≤N, M≤10,-10000≤Vi≤10000.

This blog has detailed pictures and Analysis

http://blog.csdn.net/Phenix_2015/article/details/50739989

The problem is how to judge whether a bean is in a polygon .

There's actually a good way to judge , That's a horizontal ray , Look, there are several intersections with the polygon , There's an odd number of intersections in the polygon , Otherwise, outside the polygon .

So the state is compressed , For a state , The fewer steps, the better , And then it can be more based on the compressed state , Make the shortest path of the layered graph

Each step updates the current state

But there is another situation , Even number of intersections may also be surrounded .

As shown in the figure below :

So in the process of transfer , Obviously, the horizontal movement does not affect the answer , Only vertical movement affects the position of the point

In special cases, each line segment is assumed to be open at the top and closed at the bottom , That is, only when the lower breakpoint intersects the ray can it be useful , Then the line segments in the same direction will only be counted once

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct ZYYS
{
int x,y,s;
};
const int dx[]={,,,-};
const int dy[]={,-,,};
int d,px[],py[],n,m,val[],ans;
int dist[][][],inf;
bool vis[][][];
char ss[][];
int cross(int sx,int sy,int x,int y,int s)
{int i;
int p=max(sy,y);
for (i=;i<=d;i++)
if (py[i]==p&&px[i]<x)
s^=(<<i-);
return s;
}
void spfa(int sx,int sy)
{int i,j;
queue<ZYYS>Q;
memset(dist,/,sizeof(dist));
inf=dist[][][];
memset(vis,,sizeof(vis));
Q.push((ZYYS){sx,sy,});
dist[sx][sy][]=;
while (Q.empty()==)
{
ZYYS u=Q.front();
Q.pop();
vis[u.x][u.y][u.s]=;
for (i=;i<;i++)
{
int x=u.x+dx[i],y=u.y+dy[i];
if (x<||x>n||y<||y>m) continue;
if (ss[x][y]=='#'||ss[x][y]!='') continue;
int s=u.s;
if (i<=)
s=cross(u.x,u.y,x,y,s);
if (dist[x][y][s]>dist[u.x][u.y][u.s]+)
{
dist[x][y][s]=dist[u.x][u.y][u.s]+;
if (vis[x][y][s]==)
{
vis[x][y][s]=;
Q.push((ZYYS){x,y,s});
}
}
}
}
for (i=;i<=(<<d)-;i++)
{
int res=-dist[sx][sy][i];
for (j=;j<=d;j++)
if (i&(<<j-)) res+=val[j];
ans=max(ans,res);
}
}
int main()
{int i,j;
cin>>n>>m>>d;
for (i=;i<=d;i++)
{
scanf("%d",&val[i]);
}
for (i=;i<=n;i++)
{
scanf("%s",ss[i]+);
for (j=;j<=m;j++)
{
if (ss[i][j]>''&&ss[i][j]<='')
px[ss[i][j]-'']=i,py[ss[i][j]-'']=j;
}
}
for (i=;i<=n;i++)
{
for (j=;j<=m;j++)
if (ss[i][j]=='')
{
spfa(i,j);
}
}
cout<<ans;
}

[SCOI2009] More articles about weidoudou

  1. 【BZOJ1294】[SCOI2009] Weidoudou ( Dynamic programming , Pressure )

    [BZOJ1294][SCOI2009] Weidoudou ( Dynamic programming , Pressure ) Topic BZOJ Luogu Answer key First consider how to judge whether a point is in a polygon ( It doesn't have to be convex ), We start at this point , Draw a ray in one direction , Look at it ...

  2. 【BZOJ1294】[SCOI2009] Weidoudou Bean Ray method + Pressure DP+SPFA

    [BZOJ1294][SCOI2009] Weidoudou Bean Description Input The first line has two integers N and M, Is the side length of the matrix . The second line is an integer D, Is the total number of beans . The third line contains D It's an integer V1 To VD, , respectively, ...

  3. [BZOJ1294][SCOI2009] Weidoudou Bean Ray method + Pressure dp+spfa

    1294: [SCOI2009] Weidoudou Bean Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 458  Solved: 305[Submit][Sta ...

  4. Luogu P2566 [SCOI2009] Weidoudou ( Pressure dp+spfa)

    Subject portal Answer key Σ(っ °Д °;)っ Pre knowledge Ray method : From one point to the right ( Either way is OK ) Draw a ray horizontally , If the intersection of the ray and the path is even , Then the point is not included , If it's an odd number , Then it is included .( But notice that there is a case where the ray coincides with the path ) this ...

  5. BZOJ1294: [SCOI2009] Weidoudou Bean

    subject :http://www.lydsy.com/JudgeOnline/problem.php?id=1294 Pressure dp,dis[s][i][j] From (i,j) The state of the starting circle is s One of the most short circuit . Then judge one ...

  6. 【 Answer key 】SCOI2009 Weidoudou

    A problem I wanted to do a long time ago , I've been thinking about it until today . In this question , The key point is : How to judge whether a point is in a polygon ? In fact, if the basic skills of computational geometry are solid , Should be able to give an answer quickly ( But I can't do it at all ): from ...

  7. BZOJ 1294 [SCOI2009] Weidoudou Bean —— Computational geometry

    Obviously, we can't show a path , Because it's so complicated . So we can record the effect of the path on the answer , Obviously, when the path has the same effect on the answer , The answer is better , So we can use influence instead of path . So let's consider if all the beans have been ...

  8. 【 State compression DP】SCOI2009 Weidoudou

    The main idea of the topic Logue link In a \(N×M\) In the square of the matrix of \(D\) A bean , Each bean has a different score \(V_i\). The player can choose any square as the starting grid , Each time you move, you can walk to the four adjacent grids at will , Until finally back to ...

  9. 【BZOJ】1294: [SCOI2009] Weidoudou Bean

    Answer key It's fun to jump questions randomly This is to consider how we judge that a point is in a polygon , It's just a little bit of a ray , Through an odd number of sides We just need to record a binary state that represents the parity of the number of times the ray passes through the path at each point Enumeration starting point , And then use BFS How to update dp shape ...

Random recommendation

  1. stay Salesforce Invoked by an external system Web Service

    There needs to be an external service The corresponding WSDL file (Salesforce Only local upload is supported ), And provide WSDL The document has the following two requirements : 1):wsdl There can only be one file binding,Salesforce yes ...

  2. In the domain controller FSMO role

    FSMO yes Flexible single master operation Abbreviation , It means flexible single host operation . Operation host (Operation Masters, Also known as Flexible Single Maste ...

  3. Sqli-labs less 64

    Less-64 Here sql Statement for $sql="SELECT * FROM security.users WHERE id=(($id)) LIMIT 0,1"; Example payloa ...

  4. position Absolutely

    function loginH(){ var loginH = $('.sign-main-bg .sign-main-content'); var h = loginH.height(); logi ...

  5. HTML And JS

    Web page display process flow : analysis HTML structure DOM Trees Load external JS Documents and CSS file Loading image files and other external resources JS Start running after analysis Complete JS How to express and how to implement it : <script> ...

  6. java Use dom4j and XPath analysis XML And .net operation XML Summary

    Recent research java Of dom4j package , Use dom4j Here comes the package xml file It includes three files :studentInfo.xml( To be resolved xml file ), Dom4jReadExmple.java( The main class of parsing ), ...

  7. WDCP Lower installation PHPWind

    The difference between creating an entire site and creating a new site is that creating an entire site will be generated at the same time ftp Follow mysql database Just fill in a domain name here ( If you have a domain name, fill in it If you don't have a domain name Or like me, those who go to this step to apply for a domain name can fill in ECS Public network ip Otherwise, you cannot access the new database ...

  8. JMS Way of learning ( One ): Integrate activeMQ To SpringMVC Reprint :http://www.cnblogs.com/xiaochangwei/p/5426639.html

    JMS The full name is Java Message Service, namely Java Message service . It's mainly used for messaging between producers and consumers , Producers are responsible for generating messages , The consumer is responsible for receiving the message . Applying it to actual business needs, we can ...

  9. jQuery object Wait for the operation

    ///////////////////// Next, rename the ribbon for the folder ///////////////////////// $(".wpul .rename").click(functi ...

  10. Cent os 6.8 Add Chinese font

    author : Deng Congcong Cent os 6.8 Steps to add Chinese Fonts : [root@bogon ]#yum -y install fontconfig #yum install fontconfig [root@bogon ...