http://codeforces.com/problemset/problem/821/D
Okabe likes to be able to walk through his city on a path lit by street lamps. That way, he doesn't get beaten up by schoolchildren.
Okabe's city is represented by a 2D grid of cells. Rows are numbered from 1 to n from top to bottom, and columns are numbered 1 to m from left to right. Exactly k cells in the city are lit by a street lamp. It's guaranteed that the top-left cell is lit.
Okabe starts his walk from the top-left cell, and wants to reach the bottom-right cell. Of course, Okabe will only walk on lit cells, and he can only move to adjacent cells in the up, down, left, and right directions. However, Okabe can also temporarily light all the cells in any single row or column at a time if he pays 1 coin, allowing him to walk through some cells not lit initially.
Note that Okabe can only light a single row or column at a time, and has to pay a coin every time he lights a new row or column. To change the row or column that is temporarily lit, he must stand at a cell that is lit initially. Also, once he removes his temporary light from a row or column, all cells in that row/column not initially lit are now not lit.
Help Okabe find the minimum number of coins he needs to pay to complete his walk!
Input
The first line of input contains three space-separated integers n, m, and k (2 ≤ n, m, k ≤ 104).
Each of the next k lines contains two space-separated integers ri and ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) — the row and the column of the i-th lit cell.
It is guaranteed that all k lit cells are distinct. It is guaranteed that the top-left cell is lit.
Output
Print the minimum number of coins Okabe needs to pay to complete his walk, or -1 if it's not possible.
Examples
Input
Copy
4 4 5
1 1
2 1
2 3
3 3
4 3 Output
Copy
2 Input
Copy
5 5 4
1 1
2 1
3 1
3 2 Output
Copy
-1 Input
Copy
2 2 4
1 1
1 2
2 1
2 2 Output
Copy
0 Input
Copy
5 5 4
1 1
2 2
3 3
4 4 Output
Copy
3 Note
In the first sample test, Okabe can take the path 
In the fourth sample, Okabe can take the path 
这题的题意很不好读懂，意思是：N*M的一个矩阵，现在一共有K个一直亮着的点，主人公从左上角出发，走到的点必须有亮光才行。但是不保证有亮光的点能够使得主人公到达右下角，所以他可以花费1硬币去使得一行或者一列暂时性的亮着，如果他想再次使用魔法，那么之前暂时亮着的部分就必须灭掉了，注意只能站在那k个一直亮着的点上来亮一行或一列。问最少花费多少金币，能够从左上角走到有下角。如果不能走到，输出-1.
方法1：
因为求的是最小花费，如果一行/列已经全部点亮，那么在这行上任意移动不需要花费coin，这一行/列的地位等价于一个点，因此我们把每行，每列都看作是一个点，一直亮的位置也各看作一点，这样的话图中一共有3*10^4个点，边跑Dijkstra边建图。一个恒亮点可以向四周恒亮点走，权值为0，也可以向四周不亮的地方临时点亮一行/列，权值为1。一行/列可以向周围行/列的恒亮点扩展，权值为1.
若为恒亮点，堆点存r，c。litr，litc为0.
若为一行/列，r，c为0.litr，litc相应。
d值就存在堆点里，判重用struct向bool的map映射。
这样子好像有一种情况就是：当作是"一行"而覆盖了该行的恒亮点，比如：
10001
00000
00001
这样子没办法在第1行第5列作为单独状态，直接把第一行当作一个结点， 没办法到达第2行第5列这个点了，但是显然花费1去走第一行比不上走第二行，走第二行就没问题了。
这个方法应该是没问题的，在cf跑了46ms
#include<bits/stdc++.h>
using namespace std;
#define maxn 10000+100
int n,m,k;
set<int> row[maxn],col[maxn];
vector<int> rows[maxn],cols[maxn];
struct HeapNode{
int r,c,litr,litc,d;
bool operator < (const HeapNode& x)const{
return d>x.d;
}
};
struct HeapNode2{
int r,c,litr,litc,d;
bool operator < (const HeapNode2& x)const{
if(r!=x.r)return r>x.r;
if(c!=x.c)return c>x.c;
if(litr!=x.litr)return litr>x.litr;
return litc>x.litc;
}
};
map<HeapNode2,bool> vis;
bool inside(HeapNode& x){int r=x.r,c=x.c;return r>=1&&r<=n&&c>=1&&c<=m || x.litr>=1&&x.litr<=n || x.litc>=1&&x.litc<=m;}
int dijkstra()
{
priority_queue<HeapNode> Q;
Q.push((HeapNode){1,1,0,0,0});
while(!Q.empty())
{
HeapNode x=Q.top();
Q.pop(); cout<<x.r<<" "<<x.c<<" "<<x.litr<<" "<<x.litc<<" d: "<<x.d<<endl;
HeapNode2 y=(HeapNode2){x.r,x.c,x.litr,x.litc,0};//cout<<vis.count(y)<<endl;
if(vis[y])continue;
vis[y]=1; //cout<<vis.size()<<endl;
if(x.r==n&&x.c==m || x.litr==n || x.litc==m)return x.d;
HeapNode z;
if(x.litr==0&&x.litc==0)
{
/*up*/ if(row[x.r-1].count(x.c)){z=x;z.r=x.r-1;if(inside(z))Q.push(z);}
else {
z=x;z.r=z.c=0;z.litr=x.r-1;z.d=x.d+1;if(inside(z))Q.push(z);
z=x;z.r=z.c=0;z.litc=x.c;z.d=x.d+1;if(inside(z))Q.push(z);
}
/*down*/ if(row[x.r+1].count(x.c)){z=x;z.r=x.r+1;if(inside(z))Q.push(z);}
else {
z=x;z.r=z.c=0;z.litr=x.r+1;z.d=x.d+1;if(inside(z))Q.push(z);
z=x;z.r=z.c=0;z.litc=x.c;z.d=x.d+1;if(inside(z))Q.push(z);
}
/*left*/ if(col[x.c-1].count(x.r)){z=x;z.c=x.c-1;if(inside(z))Q.push(z);}
else {
z=x;z.c=z.r=0;z.litc=x.c-1;z.d=x.d+1;if(inside(z))Q.push(z);
z=x;z.r=z.c=0;z.litr=x.r;z.d=x.d+1;if(inside(z))Q.push(z);
}
/*right*/ if(col[x.c+1].count(x.r)){z=x;z.c=x.c+1;if(inside(z))Q.push(z);}
else {
z=x;z.c=z.r=0;z.litc=x.c+1;z.d=x.d+1;if(inside(z))Q.push(z);
z=x;z.r=z.c=0;z.litr=x.r;z.d=x.d+1;if(inside(z))Q.push(z);
}
}
else if(x.litr)
{
/*up*/ for(int i=0;i<rows[x.litr-1].size();i++)
{
z.r=x.litr-1;z.c=rows[x.litr-1][i];z.litc=z.litr=0;z.d=x.d;
if(inside(z))Q.push(z);
}
/*down*/ for(int i=0;i<rows[x.litr+1].size();i++)
{
z.r=x.litr+1;z.c=rows[x.litr+1][i];z.litc=z.litr=0;z.d=x.d;
if(inside(z))Q.push(z);
}
}
else if(x.litc)
{
/*left*/ for(int i=0;i<cols[x.litc-1].size();i++)
{
z.c=x.litc-1;z.r=cols[x.litc-1][i];z.litc=z.litr=0;z.d=x.d;
if(inside(z))Q.push(z);
}
/*right*/ for(int i=0;i<cols[x.litc+1].size();i++)
{
z.c=x.litc+1;z.r=cols[x.litc+1][i];z.litc=z.litr=0;z.d=x.d;
if(inside(z))Q.push(z);
}
}
}
return -1;
}
int main()
{
freopen("input.in","r",stdin);
int a,b;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
row[a].insert(b);
col[b].insert(a);
rows[a].push_back(b);
cols[b].push_back(a);
}
cout<<dijkstra()<<endl;
return 0;
}
方法2：
以k个lit为顶点建图,若lit相邻 则边权为0,如果横坐标或者纵坐标差<=2 边权为1， 其余无法直接到达。
因为即使一行/列全都亮了，站在非lit处也无用，因为只有站在lit处才能新点亮别的行/列。
终点右下角如果lit，则没问题，否则，右下角的点可以由倒数两行、两列花费1扩展来，等价于在（n+1，m+1）lit，终点为（n+1，m+1）.
跑了1154ms，很危险，无效松弛不入队在这里非常重要。这是处理成（行，列）跑的，也可以处理成k个点跑。
#include<bits/stdc++.h>
using namespace std;
#define maxn 10000+100
struct HeapNode{
int r,c,d;
operator < (const HeapNode& x)const{
return d>x.d;
}
};
int n,m,k;
vector<int> rows[maxn],cols[maxn];
map<pair<int,int>,int> vis,d;
int dijkstra()
{
priority_queue<HeapNode> Q;
Q.push((HeapNode){1,1,0});
while(!Q.empty())
{
HeapNode x=Q.top();
Q.pop();
if(vis[make_pair(x.r,x.c)])continue;
vis[make_pair(x.r,x.c)]=1;
if(x.r==n&&x.c==m)return x.d;
HeapNode z;
for(int i=-2;i<=2;i++)
{
if(x.r+i>=1&&x.r+i<=n)for(int j=0;j<rows[x.r+i].size();j++)
{
z.r=x.r+i;
z.c=rows[x.r+i][j];
z.d=x.d;
if((abs(i)==1&&z.c==x.c)==0)z.d++;
if(z.d>=d[make_pair(z.r,z.c)])continue;
Q.push(z);
d[make_pair(z.r,z.c)]=z.d;
}
}
for(int i=-2;i<=2;i++)
{
if(x.c+i>=1&&x.c+i<=m)for(int j=0;j<cols[x.c+i].size();j++)
{
z.c=x.c+i;
z.r=cols[x.c+i][j];
z.d=x.d;
if((abs(i)==1&&z.r==x.r)==0)z.d++;
if(z.d>=d[make_pair(z.r,z.c)])continue;
Q.push(z);
d[make_pair(z.r,z.c)]=z.d;
}
}
}
return -1;
}
int main()
{
// freopen("input.in","r",stdin);
bool t_lit=0;
int a,b;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
if(a==n&&b==m)t_lit=1;
rows[a].push_back(b);
cols[b].push_back(a);
d[make_pair(a,b)]=0x3f3f3f3f;
}
if(!t_lit)
{
n++;
m++;
rows[n].push_back(m);
cols[m].push_back(n);
d[make_pair(n,m)]=0x3f3f3f3f;
}
d[make_pair(1,1)]=0;
cout<<dijkstra()<<endl;
return 0;
}
京公网安备 11010502036488号