題意：要求在一張網格圖上走出一條閉合路徑，不得將炸彈包圍進去，使圍出的總價值減去路徑長度最大。

/*類似于poj3182的做法，只不過出現了多個點，那么就用狀態壓縮的方法記錄一個集合即可。 */ #include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; char map[25][25],ch[25]; int n,m,sx,sy,tx,ty,nx,ny,gx[10],gy[10],val[10],w[1010],dp[25][25][1010],cnt=-1,ans; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; struct node{int x,y,k;}; bool ok(int j){if(nx==gx[j]&&ny<gy[j]){if(nx>tx)return true;}else if(tx==gx[j]&&ty<gy[j]){if(tx>nx)return true;}return false; } void bfs(){memset(dp,-1,sizeof(dp));queue<node> q;node u;u.x=sx;u.y=sy;u.k=0;q.push(u);dp[sx][sy][0]=0;while(!q.empty()){u=q.front();q.pop();nx=u.x;ny=u.y;int nk=u.k,tk;if(nx==sx&&ny==sy)ans=max(ans,w[nk]-dp[nx][ny][nk]);for(int i=0;i<4;i++){tx=nx+dx[i];ty=ny+dy[i];tk=nk;if(tx<1||tx>n||ty<1||ty>m||(map[tx][ty]!='.'&&map[tx][ty]!='S'))continue;for(int j=0;j<=cnt;j++)if(ok(j))tk^=(1<<j);if(dp[tx][ty][tk]==-1){dp[tx][ty][tk]=dp[nx][ny][nk]+1;node v;v.x=tx;v.y=ty;v.k=tk;q.push(v);}}} } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",ch);for(int j=1;j<=m;j++){map[i][j]=ch[j-1];if(map[i][j]=='S')sx=i,sy=j;if(map[i][j]>='1'&&map[i][j]<='8'){int t=map[i][j]-'1';++cnt;gx[t]=i;gy[t]=j;}}}for(int i=0;i<=cnt;i++)scanf("%d",&val[i]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(map[i][j]=='B'){++cnt;gx[cnt]=i;gy[cnt]=j;val[cnt]=-10000;}for(int i=0;i<(1<<cnt+1);i++)for(int j=0;j<=cnt;j++)if(i&(1<<j))w[i]+=val[j];bfs();printf("%d",ans);return 0; }

?

轉載于:https://www.cnblogs.com/harden/p/6391998.html

總結

以上是生活随笔為你收集整理的Circling Round Treasures（codeforces 375c）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。