注意到題目中有這一句話：

注意路線可以自交。為了確定一個格子是否在這條路線里面，請使用以下算法判斷： 1.假設該點的坐標為需要判斷的點為 p(i,j) ，該點不在路線上 2.從該點往任意方向作一條射線，如果與路線相交奇數(shù)次，我們就認為這個格子在這條路線里面，否則這個格子在這條路線外面。

我們設$f[i][j][k]$表示當前格子為$i,j$，所有寶藏或炸彈引出的射線與走過的路線相交總數(shù)的奇偶性的狀態(tài)為$k$的最短距離。可以通過一次bfs得到。最后，我們枚舉集合，更新答案。

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int inf=0x3f3f3f3f; int n,m,k,bx,by,dis[25][25][305],xx[4]={1,-1,0,0},yy[4]={0,0,1,-1}; char s[25][25]; bool vis[25][25][305]; struct data{int x,y,v; }a[405]; struct node{int x,y,sta;node(){}node(int x,int y,int sta):x(x),y(y),sta(sta){} }; queue<node> q; bool check(int x,int y,int nx,int ny,int id){if(x==nx){return false;}if(x==a[id].x&&y<a[id].y){return nx<x;}if(nx==a[id].x&&ny<a[id].y){return x<nx;}return false; } void bfs(){dis[bx][by][0]=0;q.push(node(bx,by,0));while(!q.empty()){int x=q.front().x,y=q.front().y,sta=q.front().sta,nx,ny,nsta;q.pop();for(int i=0;i<4;i++){nx=x+xx[i],ny=y+yy[i];if(nx<1||nx>n||ny<1||ny>m||(s[nx][ny]!='.'&&s[nx][ny]!='S')){continue;}nsta=sta;for(int j=1;j<=k;j++){if(check(x,y,nx,ny,j)){nsta^=(1<<(j-1));}}if(vis[nx][ny][nsta]){continue;}vis[nx][ny][nsta]=true;dis[nx][ny][nsta]=dis[x][y][sta]+1;q.push(node(nx,ny,nsta));}} } int gao(){int tmp,ans=0;for(int i=1;i<(1<<k);i++){if(!vis[bx][by][i]){continue;}tmp=0;for(int j=1;j<=k;j++){if(i&(1<<(j-1))){tmp+=a[j].v;}}ans=max(ans,tmp-dis[bx][by][i]);}return ans; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",s[i]+1);for(int j=1;j<=m;j++){if(s[i][j]=='S'){bx=i;by=j;}else if(isdigit(s[i][j])){a[s[i][j]-'0'].x=i;a[s[i][j]-'0'].y=j;k=max(k,s[i][j]-'0');}}}for(int i=1;i<=k;i++){scanf("%d",&a[i].v);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='B'){k++;a[k].x=i;a[k].y=j;a[k].v=-inf>>8;}}}bfs();printf("%d\n",gao());return 0; }

總結

以上是生活随笔為你收集整理的【CF375C】Circling Round Treasures【XSY1176】大包子环绕宝藏【状压dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。