漫步校園

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2091????Accepted Submission(s): 602


Problem DescriptionLL最近沉迷于AC不能自拔，每天寢室、機房兩點一線。由于長時間坐在電腦邊，缺乏運動。他決定充分利用每次從寢室到機房的時間，在校園里散散步。整個HDU校園呈方形布局，可劃分為n*n個小方格，代表各個區域。例如LL居住的18號宿舍位于校園的西北角，即方格(1,1)代表的地方，而機房所在的第三實驗樓處于東南端的(n,n)。因有多條路線可以選擇，LL希望每次的散步路線都不一樣。另外，他考慮從A區域到B區域僅當存在一條從B到機房的路線比任何一條從A到機房的路線更近(否則可能永遠都到不了機房了…)。現在他想知道的是，所有滿足要求的路線一共有多少條。你能告訴他嗎?

Input每組測試數據的第一行為n(2=<n<=50)，接下來的n行每行有n個數，代表經過每個區域所花的時間t(0<t<=50)(由于寢室與機房均在三樓，故起點與終點也得費時)。

Output針對每組測試數據，輸出總的路線數(小于2^63)。

Sample Input3
1 2 3
1 2 3
1 2 3
3
1 1 1
1 1 1
1 1 1
Sample Output1
6
AuthorLL
SourceACM暑期集訓隊練習賽（三）
Recommendlinle
4面都可以走，只能往到離終點距離近的點走。。。。。


#include <iostream>#include <cstdio>#include <cstring>#include <queue>
using namespace std;

struct po{int x;int y;};
int dir_x[4]={1,-1,0,0};int dir_y[4]={0,0,1,-1};
long long int a[55][55];long long int dp[55][55];long long int distan[55][55];int n;
void bfs(){queue<po> q;po tlp;tlp.x=n-1; ?tlp.y=n-1;q.push(tlp);
while(!q.empty()){po cur=q.front();po nxt;q.pop();for(int i=0;i<4;i++){nxt.x=cur.x+dir_x;nxt.y=cur.y+dir_y;if(nxt.y>=0&&nxt.y<n&&nxt.x>=0&&nxt.x<n&&distan[nxt.x][nxt.y]>distan[cur.x][cur.y]+a[nxt.x][nxt.y]){distan[nxt.x][nxt.y]=distan[cur.x][cur.y]+a[nxt.x][nxt.y];q.push(nxt);}}}}
long long int dfs(int x,int y){if(dp[x][y]!=0) return dp[x][y];if(x==n-1&&y==n-1) return 1;
for(int i=0;i<4;i++){int tx=x+dir_x;int ty=y+dir_y;
if(tx>=0&&tx<n&&ty>=0&&ty<n&&distan[tx][ty]<distan[x][y]){dp[x][y]+=dfs(tx,ty);}}return dp[x][y];}
int main(){while(scanf("%d",&n)!=EOF){memset(dp,0,sizeof(dp));for(int i=0;i<n;i++){for(int j=0;j<n;j++){scanf("%I64d",&a[j]);distan[j]=0x3f3f3f3f;}}distan[n-1][n-1]=0;bfs();printf("%I64d\n",dfs(0,0));}
return 0;}

轉載于:https://www.cnblogs.com/CKboss/p/3351014.html

總結

以上是生活随笔為你收集整理的HDOJ 1428 漫步校园的全部內容，希望文章能夠幫你解決所遇到的問題。

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