hdu 1428 广搜+记忆化搜索

//广搜 +深度记忆化搜索
#include<iostream>
#include<queue>
using namespace std;
#define MAX 1000000000
int n,map[51][51],dis[51][51];
__int64 dp[51][51];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
struct node
{
 int x,y;
 int time;
};
void bfs(int x1,int y1) //广搜每个点到终点的最短距离
{
    queue<node> s;
 node a,b;
 a.x=x1;
 a.y=y1;
 a.time=map[x1][y1];
 s.push(a);
 while(!s.empty())
 {
  b=s.front();
  s.pop();
  for(int i=0;i<4;i++)
  {
   a.x=b.x+dir[i][0];
   a.y=b.y+dir[i][1];
   if(a.x>0 && a.x<=n && a.y>0 && a.y<=n && (b.time+map[a.x][a.y])<dis[a.x][a.y])
   {
    a.time=b.time+map[a.x][a.y];
                dis[a.x][a.y]=a.time;
    s.push(a);
   }
  }
 }
}
__int64 dfs(int x,int y) //记忆化搜索最多的路径 如果一个点先前搜到过就可以不用搜了
{
   if(dp[x][y]!=-1) return dp[x][y];
   __int64 ans=0;
   int x1,y1;
   for(int k=0;k<4;k++)
   {
    x1=x+dir[k][0];
    y1=y+dir[k][1];
    if(x1>0 && x1<=n && y1>0 && y1<=n && dis[x1][y1]<dis[x][y])
    {
     ans+=dfs(x1,y1);
    }
   }
   return dp[x][y]=ans;

}
int main()
{
 int i,j;
// freopen("E:\\test.txt","r",stdin);
 while(cin>>n)
 {
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
   {
    cin>>map[i][j];
    dis[i][j]=MAX;
   }
  }
  dis[n][n]=map[n][n];
  bfs(n,n);
  memset(dp,-1,sizeof(dp));
  dp[n][n]=1;
  dfs(1,1);
     printf("%I64d\n",dp[1][1]);
 }
 return 0;
}