漫步校园

Problem Description

LL最近沉迷于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 Input

3 1 2 3 1 2 3 1 2 3 3 1 1 1 1 1 1 1 1 1

Sample Output

1 6

题解：设F[i][j]表示，从（i，j），跑到终点的方案数，我们用spfa预处理出当前节点到终点的距离，对于距离变大的，就不可以进行状态转移，

然后记忆化搜索，把可行的地方的方案数加起来就可以了。

#include<iostream>

#include<stdio.h>

#include<queue>

#include<algorithm>

#include<stdlib.h>

#include<cstring>

#define ll long long

using namespace std;

int n;

ll mp[][],dis[][];

int addx[]={,,-,,},addy[]={,,,,-};

int have[][];

ll f[][];

void spfa(int starx,int stary){

  queue<int> xx,yy;

  while(!xx.empty()) xx.pop();

  while(!yy.empty()) yy.pop();

  xx.push(starx);

  yy.push(stary);

  dis[starx][stary]=mp[starx][stary],have[starx][stary]=;

  while(!xx.empty()){

    int nowx=xx.front();

    int nowy=yy.front();

    xx.pop(),yy.pop();

    have[nowx][nowy]=;

    for(int i=;i<=;i++){

      int tox=nowx+addx[i],toy=nowy+addy[i];

      if(tox<=||tox>n||toy>n||toy<=) continue;

      if(dis[tox][toy]>dis[nowx][nowy]+mp[tox][toy])

    {

    dis[tox][toy]=dis[nowx][nowy]+mp[tox][toy];

    //printf("nowx=%d nowy=%d tox=%d toy=%d\n",nowx,nowy,tox,toy);

    //printf("dis[nowx][nowy]=%d dis[tox][toy]=%d mp[tox][toy]=%d\n",dis[nowx][nowy],dis[tox][toy],mp[tox][toy]);

    if(have[tox][toy]==){

      xx.push(tox);

      yy.push(toy);

      have[tox][toy]=;

    }

      }

    }

  }

}

void cl(){

  memset(mp,,sizeof(mp));

  memset(f,,sizeof(f));

  memset(have,,sizeof(have));

  memset(dis,,sizeof(dis));

}

ll dp(int x,int y){

  if(f[x][y]) return f[x][y];

  if(x==n&&y==n) return ;

  ll now=;

  for(int i=;i<=;i++){

    int tox=x+addx[i];

    int toy=y+addy[i];

    if(tox<=||tox>n||toy>n||toy<=) continue;

    if(dis[tox][toy]<dis[x][y]) now+=dp(tox,toy);

  }

  return f[x][y]=now;

}

int main(){

  while(scanf("%d",&n)!=EOF){

    cl();

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

    cin>>mp[i][j];

    spfa(n,n);

    printf("%lld\n",dp(,));

  }

}

巴特西

HDU 1428漫步校园

漫步校园

最新文章

热门文章