题意:
给你一个地图,上面有一些宝石、炸弹,让你从一个点出发回到这个点,使圈起来的宝石的价值-步数最大,并且不能圈到炸弹,能够圈到‘#’,一个点允许重复走。
思路:
就是 poj3182 的加强版,建议先做这个题,可以参考:poj 3182 题解
预处理每个圈住宝石的状态的价值,炸弹可当做价值为负无穷的宝石,取dp[x][y][k]判重,x、y为位置,k为圈住宝石的状态,剩下的就是怎样判断一个路径圈住宝石的状态了,方法是过点做一条射线,这个射线与多边形交奇数次为在多边形内,偶数次则为多边形外,具体操作只需要虚拟的射线就够了。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <map> #include <stack> #include <vector> #include <set> #include <queue> //#pragma comment (linker,"/STACK:102400000,102400000") #define maxn 25 #define mod 1000000007 #define INF 0x3f3f3f3f #define OO 0xbfbfbfbf using namespace std; typedef long long ll; int n,m,ans,cnt,flag,tot; int sx,sy; int dx[]= {-1,1,0,0}; int dy[]= {0,0,-1,1}; int dp[maxn][maxn][1<<8]; int val[8],w[1<<8]; int gx[8],gy[8]; char mp[maxn][maxn]; char s[maxn]; struct Node { int x,y,k; } cur,now; bool issur(int nx,int ny,int tx,int ty,int j) { if(nx==gx[j]&&ny<gy[j]) { if(tx<gx[j]) return true ; } else if(tx==gx[j]&&ty<gy[j]) { if(nx<gx[j]) return true ; } return false ; } void bfs() { int i,j,t,k,nx,ny,tx,ty,nk; queue<Node>q; memset(dp,-1,sizeof(dp)); ans=-INF; cur.x=sx; cur.y=sy; cur.k=0; dp[sx][sy][0]=0; q.push(cur); while(!q.empty()) { now=q.front(); q.pop(); nx=now.x; ny=now.y; nk=now.k; if(nx==sx&&ny==sy) ans=max(ans,w[nk]-dp[nx][ny][nk]); for(i=0; i<4; i++) { tx=nx+dx[i]; ty=ny+dy[i]; k=nk; if(tx<1||tx>n||ty<1||ty>m) continue ; if(!(mp[tx][ty]=='S'||mp[tx][ty]=='.')) continue ; for(j=0;j<=cnt;j++) { if(issur(nx,ny,tx,ty,j)) k^=(1<<j); } if(dp[tx][ty][k]!=-1&&dp[tx][ty][k]<=dp[nx][ny][nk]+1) continue ; cur.x=tx; cur.y=ty; cur.k=k; dp[tx][ty][k]=dp[nx][ny][nk]+1; q.push(cur); } } } int main() { int i,j,t; while(~scanf("%d%d",&n,&m)) { cnt=-1; for(i=1; i<=n; i++) { scanf("%s",s); for(j=1; j<=m; j++) { mp[i][j]=s[j-1]; if(mp[i][j]=='S') sx=i,sy=j; if(mp[i][j]>='1'&&mp[i][j]<='8') { t=mp[i][j]-'1'; cnt++; gx[t]=i,gy[t]=j; } } } for(i=0;i<=cnt;i++) { scanf("%d",&val[i]); } for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { if(mp[i][j]=='B') gx[++cnt]=i,gy[cnt]=j,val[cnt]=-10000; } } memset(w,0,sizeof(w)); tot=1<<(cnt+1); for(i=0;i<tot;i++) { for(j=0;j<=cnt;j++) { if(i&(1<<j)) w[i]+=val[j]; } } bfs(); printf("%d\n",ans); } return 0; } /* 3 3 ... SB. ... 10 11 ........S.. ........... 5........1. .7#........ ...64.#.... ........... ..........# .2......... .....3..... ........... -9 33 9 -20 12 10 -29 ans:0 8 */