題意：“他考慮從A區(qū)域到B區(qū)域僅當(dāng)存在一條從B到機(jī)房的路線比任何一條從A到機(jī)房的路線更近(否則可能永遠(yuǎn)都到不了機(jī)房了…”這句話一定要理解清楚。就是說，對(duì)于當(dāng)前位置，如果下一個(gè)狀態(tài)與終點(diǎn)的最短距離大于或者等于當(dāng)前位置到終點(diǎn)的最短距離，那么這個(gè)下一個(gè)狀態(tài)是不可取的！到此，就能明白，此題就是求出所有點(diǎn)與終點(diǎn)的最短距離，然后再從起點(diǎn)進(jìn)行記憶化搜索。

這道題目值得注意，它有用廣搜的dj，很有用的一個(gè)東東......

用廣搜實(shí)現(xiàn)的dj，如果是用一般的dj，會(huì)發(fā)現(xiàn)構(gòu)圖很麻煩，因?yàn)樗皇锹窂綆?quán)值，而是自身帶權(quán)值。寫起來只要注意，在點(diǎn)出隊(duì)列的生活將其標(biāo)記為0，在要壓入隊(duì)列的時(shí)候，判斷其標(biāo)記是否為0，為0表示隊(duì)列中木有這個(gè)點(diǎn)，則壓入........

?

#include<iostream> #include<stdio.h> #include<string.h> #include<queue> using namespace std; typedef __int64 ss; #define maxx 100000000 struct node {ss x,y; }; ss n,t[4][2]={1,0,-1,0,0,1,0,-1}; ss dis[100][100],vist[100][100],dp[100][100],a[100][100]; void dj() {queue<node>q;for(ss i=0;i<=n;i++)for(ss j=0;j<=n;j++)dis[i][j]=maxx;dis[n][n]=a[n][n];memset(vist,0,sizeof(vist));vist[n][n]=1;node tmp;tmp.x=n;tmp.y=n;q.push(tmp);while(!q.empty()){node tmp1=q.front();q.pop();vist[tmp1.x][tmp1.y]=0;for(ss i=0;i<4;i++){ss xx=tmp1.x+t[i][0];ss yy=tmp1.y+t[i][1];if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&dis[xx][yy]>dis[tmp1.x][tmp1.y]+a[xx][yy]){dis[xx][yy]=dis[tmp1.x][tmp1.y]+a[xx][yy];if(!vist[xx][yy]){node tmp2;tmp2.x=xx;tmp2.y=yy;q.push(tmp2);vist[xx][yy]=1;}}}} } ss dfs(ss x,ss y) {ss ans=0;if(!dp[x][y]){for(ss i=0;i<4;i++){ss xx=x+t[i][0];ss yy=y+t[i][1];if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&dis[xx][yy]<dis[x][y]){ans+=dfs(xx,yy);}}dp[x][y]=ans;}return dp[x][y]; } int main() {while(scanf("%I64d",&n)>0){for(ss i=1;i<=n;i++)for(ss j=1;j<=n;j++)scanf("%I64d",&a[i][j]);dj();//for(int i=1;i<=n;i++)//for(int j=1;j<=n;j++)//printf("%I64d\t",dis[i][j]);memset(dp,0,sizeof(dp));dp[n][n]=1;ss sum=dfs(1,1);printf("%I64d\n",sum);}return 0; }

?

?

?

總結(jié)

以上是生活随笔為你收集整理的hdu1428(记忆化搜索)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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