題意是給你n*m的矩陣 每個單位有一個數，-1表示不能走 》=0表示有有多少個能量能獲得 問從左上角到右下角能獲得的做大能量值（走一步消耗1單位能量）
思路： 先bfs求出所有線之間的最短距離（當然 有用的只有有能量值的點和起點，終點） 然後狀態壓縮dp 找到最大能量值 這裡有幾個注意的地方
狀態盡量從1開始 減少數組的空間（爆了一次） 其次是bfs是只搜有能量的點 其它都差不多；
#include#include #include #include using namespace std; #define INF 0x3f3f3f3f int map[300][300],dis[25][25],mark[300][300],leap[300][300]; int dir[4][2]={0,1,0,-1,1,0,-1,0}; int coord[25][3],dp[1<<18][20],n,m; struct node { int x,y; int step; }a,b; int min(int a,int b) { return a<b?a:b; } int bfs(int k) { int i; a.x=coord[k][1]; a.y=coord[k][2]; a.step=0; queue<node>q; memset(mark,0,sizeof(mark)); mark[a.x][a.y]=1; q.push(a); while(!q.empty()) { b=q.front(); q.pop(); for(i=0;i<4;i++) { a.x=b.x+dir[i][0]; a.y=b.y+dir[i][1]; a.step=b.step+1; if(a.x<=0||a.x>n||a.y<=0||a.y>m) continue; if(map[a.x][a.y]==-1) continue; if(mark[a.x][a.y]==0) { mark[a.x][a.y]=1; dis[k][leap[a.x][a.y]]=dis[leap[a.x][a.y]][k]=a.step; q.push(a); } } } return 0; } int max(int a,int b) { return a>b?a:b; } int main() { int i,j; while(~scanf("%d%d",&n,&m)) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&map[i][j]); leap[i][j]=-1; } if(map[1][1]==0&&(n>1||m>1)) {printf("you loss!\n");continue;} else if(n==1&&m==1) {printf("%d\n",map[1][1]);continue;} int t=-1; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(map[i][j]>0) { coord[++t][1]=i; coord[t][2]=j; leap[i][j]=t; } } if(map[n][m]==0) { coord[++t][1]=n; coord[t][2]=m; leap[n][m]=t; } memset(dis,INF,sizeof(dis)); for(i=0;i<t;i++) { dis[i][i]=0; bfs(i); } dis[t][t]=0; memset(dp,-1,sizeof(dp)); dp[1][0]=map[1][1]; int k=(1<<(t+1)); int Max=-1; for(i=1;i<k;i++) { for(j=0;j<=t;j++) { if((i&(1<<j))==0) continue; if(dp[i][j]<0) continue;//開始少了這句超時了一次 for(int x=0;x<=t;x++) { if(x==j) continue; if(dp[i][j]<dis[j][x]) continue; if((i&(1<<x))!=0) continue; dp[i|(1<<x)][x]=max(dp[i|(1<<x)][x],dp[i][j]-dis[x][j]+map[coord[x][1]][coord[x][2]]); Max=max(Max,dp[i|(1<<x)][x]-dis[x][t]); //printf("^^^ %d\n",Max); } } } if(Max<0) printf("you loss!\n"); else printf("%d\n",Max); } return 0; }
