BFS預處理出包括起點和終點以及所有水果的距離，然后狀態(tài)壓縮DP.
#include <stdio.h>
#include <ctime>
#include <stdlib.h>
#include <string.h>
const int N = 260;
const int M = 20;
struct node {
int x, y;
void get(int a, int b) {
x = a; y = b;
}
void write() {
printf("%d %d\n", x, y);
}
};
int n, m;
int ini[N][N];
int id[N][N];
node vaild[M];
int vlen;
bool h[N][N];
int dis[M][M];
int mv[4][2] = {{1,0}, {-1, 0}, {0, 1}, {0, -1}};
int f[18][(1<<18)];
int s[(1<<18)][18];
int slen[(1<<18)][2];
int w[M];
inline int max(int a, int b ){ return a > b ? a : b;}
void init() {
memset( id, 0, sizeof( id ));
vlen = 0;
int cnt = 0;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
scanf("%d", ini[i] + j);
if( i == 0 && j == 0 ) {
vaild[vlen++].get(i, j);
id[i][j] = ++cnt;
}
else if( ini[i][j] > 0 ) {
vaild[vlen++].get(i, j);
id[i][j] = ++cnt;
}
else if( i == n-1 && j == m-1 ) {
vaild[vlen++].get(i, j);
id[i][j] = ++cnt;
}
}
}
}
node que[N*N*10];
int head, tail, flag, step;
inline void pre() {
head = tail = 0;
memset(h, 0, sizeof( h));
step = 0;
}
inline bool isok(node a) {
if( a.x < 0 || a.x >= n || a.y < 0 || a.y >= m ) return false;
if( ini[a.x][a.y] == -1 || h[a.x][a.y] ) return false;
return true;
}
inline void expand(node now) {
for(int i = 0; i < 4; i ++) {
node next;
next.get(now.x+mv[i][0], now.y+mv[i][1]);
if( isok(next) ) {
que[++tail] = next;
h[next.x][next.y] = 1;
}
}
}
void bfs() {
memset(dis, -1 ,sizeof(dis));
for(int i = 0; i < vlen; i ++) {
pre();
node ori = vaild[i];
que[++tail] = ori;
h[ori.x][ori.y] = 1;
while( head < tail ) {
int size = tail - head;
while( size -- ) {
node now = que[++head];
expand(now);
int d = id[now.x][now.y];
if( d > 0 ) dis[i][d-1] = step;
}
step ++;
}
}
}
void dp() {
if( dis[0][vlen-1] < 0 ) {
puts("you loss!");
return;
}
int mm = (1<<(vlen-1));
for(int i = 0; i < mm; i ++) for(int j = 0 ; j < vlen-1; j ++) f[j][i] = -1;
for(int i = 0; i < vlen; i ++) {
w[i] = ini[vaild[i].x][vaild[i].y];
}
for(int i = 0; i < vlen-1; i ++)
if( w[0] >= dis[0][i+1] && dis[0][i+1] >= 0) {
f[i][1<<i] = w[0] + w[i+1] -dis[0][i+1];
}
for(int i = 1; i < mm; i ++) {
int lenj = slen[i][0];
int lenk = slen[i][1];
for(int jj = 0; jj < lenj; jj ++) {
int j = s[i][jj];
if( j < vlen-1)
for(int kk = lenj; kk < lenj+lenk; kk ++) {
int k = s[i][kk];
int news = ( i|(1<<j) );
if( k<vlen-1 && f[k][i] >= dis[k+1][j+1] && dis[k+1][j+1] >= 0 ) {
f[j][i|(1<<j)] = max( f[j][i|(1<<j)], f[k][i] - dis[k+1][j+1]+ w[j+1] );
}
}
}
}
int ans = -1, t;
if( w[0] >= dis[0][vlen-1] && dis[0][vlen-1]>=0 ) ans = w[0] - dis[0][vlen-1];
for(int i = 1; i < mm; i ++){
for(int j = 0; j < vlen-1; j ++) {
t = dis[j+1][vlen-1];
if( t >= 0 && f[j][i] >= t )
ans = max(ans, f[j][i]-t);
}
}
if(w[0] == 0) ans = -1;
if( dis[0][vlen-1] == 0 ) ans = w[0];
if( ans < 0 ) puts("you loss!");
else printf("%d\n", ans);
}
void best() {
int mm = (1<<17);
for(int i = 1; i < mm; i ++) {
slen[i][0] = slen[i][1] = 0;
for(int j = 0; j < 17; j ++) if( (i & (1<<j)) == 0 ) s[i][slen[i][0]++] = j;
for(int j = 0; j < 17; j ++) if( (i & (1<<j)) != 0 ) s[i][slen[i][0]+slen[i][1]++] = j;
}
}
int main() {
best();
int tt = clock();
freopen("in.txt","r",stdin);
while( scanf("%d %d", &n, &m) != EOF) {
init();
bfs();
dp();
}
printf("%d\n", clock() - tt);
while(1);
}