hdu1428漫步校园

#include <queue>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <cstdio>

using namespace std;

int n;

const int maxn = 60;

const int INF = 0x7fffffff;

struct node {

	int x, y;

	int d;

	int mind;

};

const int dx[] = {0, 1, 0, -1};

const int dy[] = {1, 0, -1, 0};

node map[maxn][maxn];

queue<node> Q;

long long vis[maxn][maxn];

void input()

{

	while(!Q.empty()) {

		Q.pop();

	}

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

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

			scanf("%d", &map[i][j].d);

		    map[i][j].mind = INF;

			map[i][j].x = i;

			map[i][j].y = j;

		}

	}

}

void bfs()

{

	node tmp, next;

	tmp.d = map[n][n].d;

	tmp.x = n;

	tmp.y = n;

	tmp.mind = map[n][n].d;

	map[n][n].mind = map[n][n].d;//init the beginning

	Q.push(tmp);

	while(!Q.empty())

	{

		node now = Q.front();

		Q.pop();

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

			next.x = now.x + dx[i];

			next.y = now.y + dy[i];

			if(next.x<1 || next.x>n || next.y<1 || next.y>n) continue;

			if(map[next.x][next.y].mind > map[now.x][now.y].mind + map[next.x][next.y].d) {

				map[next.x][next.y].mind = map[now.x][now.y].mind + map[next.x][next.y].d;

				Q.push(map[next.x][next.y]);

			}

		}

	}

}

long long dfs(int x, int y) //int wa

{

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

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

	int newx, newy;

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

		newx = x + dx[i];

		newy = y + dy[i];

		if(newx < 1 || newx > n || newy < 1 || newy > n) continue;

		if(map[x][y].mind > map[newx][newy].mind) {

			vis[x][y] += dfs(newx, newy);

		}

	}

	return vis[x][y];

}

int main()

{

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

		input();

		bfs();

		memset(vis, 0, sizeof(vis));

		long long res = dfs(1, 1);

		cout << res << endl;

	}

	return 0;

}