题解 CF821D 【Okabe and City】

其实，这道题不用long long也能AC。

题意是给你一个矩阵，有一些格子被点亮有一些没有，每一次只能在被点亮的格子上面走。

然后你每一次都可以选择点亮一行或一排（非永久），现在问你最少点多少次可以走到终点？

思路十分好想。

我们把相邻的格子边权设为0，把不相邻但只差一行的格子之间边权设为1。（其他情况都不能直接到达）

然后跑一下SPFA就可以了。

但是需要考虑一个特例：终点有没有被点亮。

如果点了的话那没关系，没点的话得把(n+1,m+1)设为点亮的点。（要不然我们走不到终点不是吗）

AC代码如下：

11149ms/192kb

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

using namespace std;

namespace StandardIO{

	template<typename T>inline void read(T &x){

		x=0;T f=1;char c=getchar();

		for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

		for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';

		x*=f;

	}

	template<typename T>inline void write(T x){

		if(x<0)putchar('-'),x*=-1;

		if(x>=10)write(x/10);

		putchar(x%10+'0');

	}

}

using namespace StandardIO;

namespace Solve{

	const int N=10100;

	const int INF=0x3f3f3f3f;

	int n,m,k;

	struct node{

		int from,to;

	}edge[N];

	int dis[N],vis[N];

	inline int spfa(){

		for(register int i=1;i<=k;++i)dis[i]=INF;

		queue<int>q;q.push(1);

		vis[1]=1,dis[1]=0;

		while(!q.empty()){

			int to=q.front();q.pop();

			vis[to]=0;

			for(register int i=1;i<=k;++i){

				if(to==i)continue;

				int val=INF;

				int dx=abs(edge[to].from-edge[i].from),dy=abs(edge[to].to-edge[i].to);

				if(dx+dy==1)val=0;

				else if(dx<=2||dy<=2)val=1;

				if(dis[i]>dis[to]+val){

					dis[i]=dis[to]+val;

					if(!vis[i]){

						q.push(i),vis[i]=1;

					}

				}

			}

		}

		if(dis[k]!=INF)return dis[k];

		return -1;

	}

	inline void solve(){

		read(n),read(m),read(k);

		int flag=0;

		for(register int i=1;i<=k;++i){

			read(edge[i].from),read(edge[i].to);

			if(edge[i].from==n&&edge[i].to==m)flag=1;

		}

		if(!flag)edge[++k].from=n+1,edge[k].to=m+1;

		write(spfa());

	}

}

using namespace Solve;

int main(){

	solve();

}

巴特西

题解 CF821D 【Okabe and City】

最新文章

热门文章