題意：用一個(gè)案例來解釋

4 4 5

S.X.

..X.

..XD

.... 在這個(gè)案例中，是一個(gè)4*4的地圖。 . 表示可走的地方， X 表示不可走的地方，S表示起始點(diǎn)，D表示目標(biāo)點(diǎn)。沒走到一個(gè)點(diǎn)之后。這個(gè)點(diǎn)就不可走啦。起始點(diǎn)的時(shí)間是0，那么問 在 時(shí)間剛好是 5 的時(shí)候能不能走到 D ，對(duì)于這個(gè)案例來說顯然不能

題解：這里學(xué)習(xí)到了一個(gè)剪枝 ： 路徑剪枝，是看了這個(gè)博客的解釋，結(jié)合題目講了兩個(gè)剪枝，講得非常具體：http://acm.hdu.edu.cn/forum/read.php?tid=6158

另一個(gè)地方須要注意的就要是，在用到 abs 函數(shù)的時(shí)候，默認(rèn) abs 參數(shù)是不包含 int 類型的，會(huì)報(bào)錯(cuò)，須要加入 stdlib.h 頭文件

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring>using namespace std;int N,M,T; char map[10][10]; bool flag[10][10];struct Node{int x,y,step; }S,E;int vis[4][2] = {1,0,-1,0,0,1,0,-1}; bool OK;//用來標(biāo)記是否在搜索中找到，假設(shè)找到了就能夠直接推斷，在遞歸中退出bool dfs(Node n) {if(n.x == E.x && n.y == E.y && n.step == T){OK = true; return true;}//路徑剪枝int temp =T-n.step-abs(n.x-E.x)-abs(n.y-E.y);if(temp < 0 || temp&1) return false;for(int i = 0; i < 4; i ++){Node pre;pre.x = n.x+vis[i][0]; pre.y = n.y+vis[i][1];if(pre.x>=0 && pre.x<N && pre.y>=0 && pre.y < M && map[pre.x][pre.y] != 'X'){pre.step = n.step+1;map[pre.x][pre.y] = 'X';dfs(pre);if(OK) return true;map[pre.x][pre.y] = '.';}}return false; }int main() {while(scanf("%d%d%d",&N,&M,&T)){if(!N && !M && !T) break;for(int i = 0; i < N; i ++) scanf("%s",map[i]);//cin >> map[i];for(int i = 0; i < N; i ++){for(int j = 0; j < M; j ++){if(map[i][j] == 'S') S.x = i,S.y = j;if(map[i][j] == 'D') E.x = i,E.y = j;}}memset(flag,false,sizeof(flag));map[S.x][S.y] = 'X';S.step = 0;OK = false;if(dfs(S)) cout << "YES" <<endl;else cout << "NO" <<endl;}return 0; }
《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的hdu1010 dfs+路径剪枝的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。