Link

题意：给出$n*m$大小的地图，已有$k$盏灯亮，人从左上角出发，右下角结束，期间必须走路灯点亮的地方，他可以在任意时刻消耗一枚硬币点亮一行或一列灯，他最多同时点亮一行或一列灯，要想点亮别的行列时，原先灯的状态将还原。

思路：看似很繁琐的题目，其实重点在于每次只能进行一次操作，那么只需要边走边考虑下一步到达的点即可。由于可任选行列，那么意味着下一个点只要和当前位置x和y坐标之差都不超过2，那么都能到达，在此情况上，坐标差之和为1说明相邻不需要消耗硬币，其余情况均消耗一枚硬币。跑个最短路就行了，数据小，BFS都行。

/** @Date    : 2017-07-04 20:40:33  * @FileName: 821D 图 最短路.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <bits/stdc++.h>#define LL long long#define PII pair#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 3e5+20;const double eps = 1e-8;LL dis[N];LL vis[N];int n, m, k;struct yuu{	int x, y;}a[N];void spfa(int s){	MMI(dis);	MMF(vis);	queueq;	q.push(s);	dis[s] = 0;	vis[s] = 1;	while(!q.empty())	{		int nw = q.front();		q.pop();		vis[nw] = 0;		for(int i = 1; i <= k; i++)		{			LL tmp;			int dx = abs(a[i].x - a[nw].x);			int dy = abs(a[i].y - a[nw].y);			if(dx + dy == 1)//相邻				tmp = 0;			else if(dx <= 2 || dy <= 2)//距离等于2的中间亮一行连接				tmp = 1;			else 				tmp = INF;							if(dis[i] > dis[nw] + tmp)			{				dis[i] = dis[nw] + tmp;				if(!vis[i])					vis[i] = 1, q.push(i);			}		}	}}int main(){	while(cin >> n >> m >> k)	{		for(int i = 1; i <= k; i++) scanf("%d%d", &a[i].x, &a[i].y);				int flag = 0;		for(int i = 1; i <= k && !flag; i++)			if(a[i].x == n && a[i].y == m)				flag = 1;						if(!flag)//如果终点是不亮的增加一个点，相当于权值+1		{			k++;			a[k].x = n + 1, a[k].y = m + 1;		}		spfa(1);		LL ans = dis[k];		if(ans >= INF)			ans = -1;		printf("%lld\n", ans);	}    return 0;}

CF821 D. Okabe and City 图 最短路