题目链接：
http://codeforces.com/contest/821/problem/D
题目大意：
现在给你N*M的一个矩阵，现在上边一共有K个永恒亮着的点，主人公从左上角出发，走到的点必须有亮光才行。
但是现在不保证有亮光的点能够使得主人公到达右下角，所以他可以花费1单位金币去使得一行或者一列暂时性的亮着，如果他想再次使用魔法，那么之前暂时亮着的部分就必须灭掉了。
问他最少花费多少金币，能够从左上角走到右下角。
如果不能走到，输出-1.
分析：
这题可以将k个点看做图中的点，由于站在一个初始亮的点上可以将一行或一列变亮，所以我们可以在这个点上，点亮相邻的一行或一列，然后再到相邻行列上的任意点，或者点亮这个点所在的行或列。这样就能够想到了再引入行和列作为图中的点，然后以k个点和相邻的行和列作为图的顶点建图。从一个点到相邻行列花费是1，反向花费是0，然后跑一遍最短路就可以了。
总结：灵活抽象运用最短路的好题！
具体实现请看代码:
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int maxn = 1e6+5;
const int INF = 0x3f3f3f3f;
pii p[maxn];
map<pii, int> mp;
struct edge
{int to, cost;edge(){}edge(int to, int cost):to(to), cost(cost){}
};
vector<edge> G[maxn];
int nx[5] = {1, -1, 0, 0};
int ny[5] = {0, 0, 1, -1};
int dis[maxn];
bool vis[maxn];
void dijkstra(int s)
{priority_queue<pii, vector<pii>, greater<pii> > q;memset(dis, 63, sizeof(dis));memset(vis, false, sizeof(vis));dis[s] = 0;q.push(pii(0, s));while(!q.empty()){pii tem = q.top();q.pop();int v = tem.second;if(vis[v]) continue;
// if(dis[v] < tem.second) continue;vis[v] = true;for(int i = 0; i < G[v].size(); i++){edge e = G[v][i];if(dis[e.to] > dis[v] + e.cost){dis[e.to] = dis[v] + e.cost;q.push(pii(dis[e.to], e.to));}}}
}
int main()
{int n, m, k;scanf("%d%d%d", &n, &m, &k);mp.clear();int dd = 1e4+5;for(int i = 1; i <= k; i++){int r, c;scanf("%d%d", &r, &c);//从点到相邻边G[i].push_back(edge(r+dd, 1));G[i].push_back(edge(c+dd*2, 1));G[i].push_back(edge(r+dd+1, 1));G[i].push_back(edge(r+dd-1, 1));G[i].push_back(edge(c+dd*2+1, 1));G[i].push_back(edge(c+dd*2-1, 1));//从相邻边到点G[r+dd].push_back(edge(i, 0));G[c+dd*2].push_back(edge(i, 0));G[r+dd-1].push_back(edge(i, 0));G[r+dd+1].push_back(edge(i, 0));G[c+dd*2+1].push_back(edge(i, 0));G[c+dd*2-1].push_back(edge(i, 0));p[i] = pii(r, c);mp[p[i]] = i;}for(int i = 1; i <= k; i++)for(int j = 0; j < 4; j++){int x = p[i].first + nx[j];int y = p[i].second + ny[j];//相邻点if(mp.find(pii(x, y)) != mp.end())G[i].push_back(edge(mp[pii(x, y)], 0));}if(mp.find(pii(n, m)) == mp.end()){G[n+dd].push_back(edge(k+1, 0));G[m+dd*2].push_back(edge(k+1, 0));}dijkstra(mp[pii(1, 1)]);int ans;if(mp.find(pii(n, m)) == mp.end())ans = dis[k+1];elseans = dis[mp[pii(n, m)]];if(ans == INF)ans = -1;printf("%d\n", ans);return 0;
}