【luogu P1606 [USACO07FEB]荷叶塘Lilypad Pond】题解

题目链接：https://www.luogu.org/problemnew/show/P1606

这个题。。第一问很好想，但是第二问，如果要跑最短路计数的话，零边权的花怎么办？

不如这样想，如果这个点能到花的话，那把他和从花能到的一个点边权连成一，好比两条路径共为1：一条为1一条为0的路径

但在实际操作的时候，一朵花是可以到另一朵花的！

电风扇好啊

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define int long long

using namespace std;

const int maxn = 2000000;

ll a[50][50], n, m, s, t, ans[maxn], dis[maxn];

bool vis[maxn], used[maxn];

ll dx[9] = {0,-2,-2,-1,+1,+2,+2,+1,-1}, dy[9] = {0,-1,+1,+2,+2,+1,-1,-2,-2};

queue<ll> q;

struct edge{

	ll to, next, len;

}e[maxn<<2];

ll head[maxn], cnt;

void add(ll u, ll v, ll w)

{

	e[++cnt].len = w; e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt;

}

void SPFA()

{

	for(ll i = 1; i <= n*m; i++) dis[i] = 9223372036854775806;

	q.push(s);

	vis[s] = 1;

	dis[s] = 0;

	ans[s] = 1;

	while(!q.empty())

	{

		ll now = q.front(); q.pop();

		vis[now] = 0;

		for(ll i = head[now]; i != -1; i = e[i].next)

		{

			ll v = e[i].to;

			if(dis[v] > dis[now] + e[i].len)

			{

				ans[v] = ans[now];

				dis[v] = dis[now] + e[i].len;

				if(!vis[v])

				{

					q.push(v);

					vis[v] = 1;

				}

			}

			else if(dis[v] == dis[now] + e[i].len) ans[v] += ans[now];

		}

	}

}

void dfs(ll fx, ll fy, ll tx, ll ty)

{

	used[(tx-1)*m+ty] = 1;

	for(ll i = 1; i <= 8; i++)

	{

		ll ex = tx+dx[i], ey = ty+dy[i];

		if(ex < 1 || ex > n || ey < 1 || ey > m || used[(ex-1)*m+ey]) continue;

		if(a[ex][ey] == 2) continue;

		if(a[ex][ey] == 1) dfs(fx, fy, ex, ey);

		else used[(ex-1)*m+ey] = 1, add((fx-1)*m+fy, (ex-1)*m+ey, 1);

	}

}

void init()

{

	memset(head, -1, sizeof(head));

	scanf("%lld%lld",&n,&m);

	for(ll i = 1; i <= n; i++)

		for(ll j = 1; j <= m; j++)

		{

			scanf("%lld",&a[i][j]);

			if(a[i][j] == 3)

			s = (i-1)*m+j;

			if(a[i][j] == 4)

			t = (i-1)*m+j;

		}

	for(ll i = 1; i <= n; i++)

		for(ll j = 1; j <= m; j++)

		{

			if(a[i][j] == 2 || a[i][j] == 4 || a[i][j] == 1) continue;

			memset(used, 0, sizeof(used));

			dfs(i, j, i, j);

		}

}

#undef ll

int main()

#define ll long long

{

	freopen("testdata.in","r",stdin);

	init();

	SPFA();

	if(dis[t] == 9223372036854775806) puts("-1");

	else printf("%lld\n%lld",dis[t]-1, ans[t]);

	return 0;

}

巴特西

【luogu P1606 [USACO07FEB]荷叶塘Lilypad Pond】题解

最新文章

热门文章

巴特西

【luogu P1606 [USACO07FEB]荷叶塘Lilypad Pond】 题解

最新文章

热门文章

【luogu P1606 [USACO07FEB]荷叶塘Lilypad Pond】题解