题解 P2566 【[SCOI2009]围豆豆】
xukuan
2020-10-29 12:02:15
不明白为什么有dp的标签,这题个人更倾向于状压spfa
判断点是否在多边形内：从这个点向外引一条射线，若与多边形相交了奇数次，就在它的内部，否则在外部。
为了防止各种诡异情况（比如多边形类似“凹”字，然后过他的顶点；射线与边重合不算相交），这题的射线采用向正右方的射线
先来设计最短路的状态
用$f_{x,y,S}$表示当前在点$(x,y)$,状态为S要走的最短步数
$1 \leq D \leq 9$，显然状压，S的第i位表示数字i是否在多边形内
然后设计状态转移
如果当前状态为S，下一个点的状态为T，怎么从S推出T
1. 横着走：T=S
2. 竖着走：如果有一个数字在当前点的正左侧或者下一个点的正左侧（你不能确定下一步会不会转弯，因为这样就变成了重合，所以要算上当前点），那么改变它的状态（原来不在图形内的变成在内，在内的变成在外）
搜索题的特点是思路简单代码长，这题就说到这里，直接上代码
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=15,D=10;
const ll dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
ll n,m,k,ans,a[N],g[1<<D],f[N][N][1<<D],v[N][N][1<<D];
char s[N][N];
struct{
ll x,y;
}place[N];
struct node{
ll x,y,S;
};
queue<node> q;
inline bool check(ll x,ll y){
return x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]=='0';
}
inline ll getT(ll x,ll y,ll X,ll Y,ll S){
ll T=S;
for(ll i=1; i<=k; i++){
if(((x==place[i].x&&X<place[i].x)||(x<place[i].x&&X==place[i].x))&&Y>place[i].y) T^=1<<(i-1);
}
return T;
}
inline void spfa(node S){
while(!q.empty()) q.pop();
memset(v,0,sizeof(v));
memset(f,0x3f,sizeof(f));
q.push(S); v[S.x][S.y][S.S]=1;
f[S.x][S.y][S.S]=0;
while(!q.empty()){
ll x=q.front().x,y=q.front().y,S=q.front().S; q.pop();
v[x][y][S]=0;
for(ll i=0; i<4; i++){
ll X=x+dx[i],Y=y+dy[i];
if(check(X,Y)){
ll T=S;
if(i==0||i==2) T=getT(x,y,X,Y,S);
if(f[x][y][S]+1<f[X][Y][T]){
f[X][Y][T]=f[x][y][S]+1;
if(!v[X][Y][T]){
q.push(node{X,Y,T});
v[X][Y][T]=1;
}
}
}
}
}
for(ll i=0; i<(1<<k); i++) ans=max(ans,g[i]-f[S.x][S.y][i]);
}
int main(){
cin>>n>>m>>k;
for(ll i=1; i<=k; i++) scanf("%lld",&a[i]);
for(ll i=1; i<=n; i++){
scanf("%s",s[i]+1);
for(ll j=1; j<=m; j++){
if(s[i][j]>='1'&&s[i][j]<='9'){
ll now=s[i][j]-48;
place[now].x=i;
place[now].y=j;
}
}
}
for(ll i=0; i<(1<<k); i++){
for(ll j=1; j<=k; j++){
if(i&(1<<(j-1))) g[i]+=a[j];
}
}
for(ll i=1; i<=n; i++){
for(ll j=1; j<=m; j++){
if(s[i][j]=='0') spfa(node{i,j,0});
}
}
cout<<ans<<endl;
return 0;
}
```