題意:

? ? ? ? ? ? ?給你起點,終點,圖上有墻有路還有寶物,問你在規定時間內能否能到終點,如果能問最多能撿到多少寶物.

思路:

? ? ? ? ? 看完這個題目果斷 BFS+三維的mark[][][] 第三維用二進制壓縮的思想去解決,結果TLE了,我后來在網上看了看,發現有人用二進制壓縮ac了,這更堅定了我的決心啊,不停的優化 超時 優化 超時 就這樣我超時了 50多次,我tm惡心了,直接粘了個網上說和我想法一樣的代碼交上去了,結果 TLE 了, 我 fuck ,超時了早說啊...?,可能是數據加強了.

下面說一下正解 ,觀察我們發現,題目中給的寶貝數量并不多,最多才10 ,其實我們可以先 BFS求出所有點的最短路,這些點包括 ,起點,終點,寶物,求完最短路我們其實就把這個圖壓縮成了最多 10 + 1 + 1 個點,壓縮了圖之后就是暴力DFS了,12個點壓力也有點大,所以要剪枝 , 在深搜的時候如果發現當前的可滿足ans 已經等于寶物總和了,那么不用在搜了,直接return 到最外面,或者可以再加上一個就是,當前的所用時間 + 當前到終點的時間 大于題目給的時間限制了,直接return 到上一層;?

/*
先BFS把圖壓縮,在DFS爆搜
*/


#include<stdio.h>
#include<string.h>
#include<queue>


#define N1 60
#define N2 15?


using namespace std;


typedef struct
{
? ?int x ,y ,t;
}NODE;


NODE xin ,tou;
int mark_bfs[N1][N1] ,mark_dfs[N2];
int dis[N2][N2] ,money[N2];
int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};
char map[N1][N1];
int xx ,yy ,tt ,mm ,ss ,nn;


bool ok(int x ,int y)
{
? ?if(x >= 0 && x < xx && y >= 0 && y < yy && map[x][y] != '*' && !mark_bfs[x][y])
? ?return 1;
? ?return 0;
}


void BFS(int x ,int y ,int key)// 求那幾個點之間的最短路,key當前是起始點.
{
? ?memset(mark_bfs ,0 ,sizeof(mark_bfs));
? ?mark_bfs[x][y] = 1;
? ?xin.x = x ,xin.y = y ,xin.t = 0;
? ?queue<NODE>q;
? ?q.push(xin);
? ?while(!q.empty())
? ?{
? ? ? tou = q.front();
? ? ? q.pop();
? ? ? for(int i = 0 ;i < 4 ;i ++)
? ? ? {
? ? ? ? ?xin.x = tou.x + dir[i][0];
? ? ? ? ?xin.y = tou.y + dir[i][1];
? ? ? ? ?xin.t = tou.t + 1;
? ? ? ? ?if(ok(xin.x ,xin.y))
? ? ? ? ?{
? ? ? ? ? ? mark_bfs[xin.x][xin.y] = 1;
? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? if(map[xin.x][xin.y] == '@')
? ? ? ? ? ? dis[key][0] = xin.t;
? ? ? ? ? ? if(map[xin.x][xin.y] == '<')
? ? ? ? ? ? dis[key][nn+1] = xin.t;
? ? ? ? ? ? if(map[xin.x][xin.y] >= 'A' && map[xin.x][xin.y] <= 'J')
? ? ? ? ? ? dis[key][map[xin.x][xin.y] - 64] = xin.t;
? ? ? ? ?}
? ? ? }
? ?}
? ?return ;
}


void DFS(int s ,int time ,int mon) // s是當前點 ,time是當前所用時間,mon是當前財

//富值
{
? ?if(time > tt || mm == ss) return;
? ?if(s == nn + 1 && mm < mon)
? ?mm = mon;
? ?for(int k = 1 ;k <= nn + 1 ;k ++)
? ?{
? ? ? if(!dis[s][k] || mark_dfs[k]) continue;
? ? ? mark_dfs[k] = 1;
? ? ? DFS(k ,time + dis[s][k] ,mon + money[k]);
? ? ? mark_dfs[k] = 0;
? ?}
}


int main ()
{
? ?int i ,j ,t ,cas = 1;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%d %d %d %d" ,&yy ,&xx ,&tt ,&nn);
? ? ? money[0] = money[nn+1] = 0;
? ? ? for(ss = 0 ,i = 1 ;i <= nn ;i ++)
? ? ? {
? ? ? ? ?scanf("%d" ,&money[i]);
? ? ? ? ?ss += money[i];
? ? ? }
? ? ? for(i = 0 ;i < xx ;i ++)
? ? ? scanf("%s" ,map[i]);
? ? ? memset(dis ,0 ,sizeof(dis));
? ? ? for(i = 0 ;i < xx ;i ++)
? ? ? for(j = 0 ;j < yy ;j ++)
? ? ? {

? ? ? ? ?// 起點是 0 ,終點是 n + 1 ,寶物是 1 ---- n其他的墻和路都不要了,深搜時沒有用
? ? ? ? ?if(map[i][j] == '*')
? ? ? ? ?continue;
? ? ? ? ?if(map[i][j] == '@')
? ? ? ? ?BFS(i ,j ,0);
? ? ? ? ?if(map[i][j] == '<')
? ? ? ? ?BFS(i ,j ,nn + 1);
? ? ? ? ?if(map[i][j] >= 'A' && map[i][j] <= 'J')
? ? ? ? ?BFS(i ,j ,map[i][j] - 64);
? ? ? }
? ? ? mm = -1;
? ? ? memset(mark_dfs ,0 ,sizeof(mark_dfs));
? ? ? mark_dfs[0] = 1;
? ? ? DFS(0 ,0 ,0);
? ? ? printf("Case %d:\n" ,cas ++);
? ? ? if(mm == -1)
? ? ? printf("Impossible\n");
? ? ? else
? ? ? printf("The best score is %d.\n" ,mm);
? ? ? if(t) printf("\n");
? ?}
? ?return 0;
}
? ?
? ? ??
? ? ??

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的hdu 1044 BFS(压缩图)+DFS的全部內容，希望文章能夠幫你解決所遇到的問題。

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