程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1428-漫步校園(記憶化搜索)

HDU 1428-漫步校園(記憶化搜索)

編輯：C++入門知識

HDU 1428-漫步校園(記憶化搜索)

漫步校園

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3071 Accepted Submission(s): 932

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

Input 每組測試數據的第一行為n(2=
Output 針對每組測試數據，輸出總的路線數(小於2^63)。

Sample Input

Sample Output

1
6題意比較坑。。問從（1，1）到（n，n）能走的路徑數。規定從一點(x,y)到相鄰的4個點能走的條件是該點到（n，n）的最短距離大於要到達的那個點距離（n，n）的最短距離 （最短距離可用bfs生成。。）然後爆搜即可。。要用到記憶化來加速搜索。。其中 dp[i][j] 代表在點（i，j）時滿足答案的部分解。這樣回溯的時候會很節省時間。。還有。。要用%I64d...#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll __int64
#define pp pair
using namespace std;
const int INF = 0x3f3f3f3f;
ll dp[52][52],ma[52][52],dis[52][52];
int n,dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void bfs()
{
	queue < pp > Q;
	dis[n][n]=ma[n][n];
	Q.push(make_pair(n,n));
	while(!Q.empty())
	{
		pp t=Q.front();Q.pop();
		for(int i=0;i<4;i++)
		{
			int tx=t.first+dir[i][0];
			int ty=t.second+dir[i][1];
			if(tx<1||tx>n||ty<1||ty>n)
				continue;
			if(dis[tx][ty]==-1||dis[tx][ty]>dis[t.first][t.second]+ma[tx][ty])
			{
				dis[tx][ty]=dis[t.first][t.second]+ma[tx][ty];
				Q.push(make_pair(tx,ty));
			}
		}
	}
}
ll dfs(int x,int y)
{
	if(dp[x][y])
		return dp[x][y];
	if(x==n&&y==n)
		return 1;
	for(int i=0;i<4;i++)
	{
		int tx=dir[i][0]+x;
		int ty=dir[i][1]+y;
		if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&dis[tx][ty]