题解：AT_joisc2016_j 危険なスケート
__vector__ · · 题解
考场上写出了正解，但是忘加前缀和优化，大样例不是极限数据还跑得挺快的，寄成了 65。
Solution
考虑对于点
本文仅考虑向右走的情况，其他情况本质一样。
假设
那么
-
-
-
-
- 以此类推。
对于上述第
直接这么建边就是对的，但是一次上述跳转，产生的新障碍可能会影响后面的其他跳转，为啥不会有问题？
因为如果一次横跳（就是上面描述的样子）之后，兜兜转转进行另一次横跳，并且和第一次横跳涉及到的节点交叉了，这种情况的答案一定不是最优的，算出的答案不会影响最优解，因为完全可以在第一次横跳的时候，在第一次横跳与第二次横跳交叉的节点直接开启第二次横跳。
按照上述建图方式会 TLE，还得优化。
注意到，
然后
上述若出现共同点则按照最小权值，不过直接建图最短路建出重边也无所谓。
这样优化：对于任意点
对于
明显地上述做法可以得到最优解，并且稍微画一下或想象一下图的样子可以发现这样绝对不会让答案算小。
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
void ioopti(){
ios::sync_with_stdio(0);
cin.tie(0);
}
void io(){
freopen("skate.in","r",stdin);
freopen("skate.out","w",stdout);
}
const int maxn=1e3+5;
int n,m;
char s[maxn][maxn];
int r1,c1,r2,c2;
vector<pair<pii,int> > g[maxn][maxn];
int r_lstblk[maxn][maxn],r_nxtblk[maxn][maxn],c_lstblk[maxn][maxn],c_nxtblk[maxn][maxn];
bitset<maxn> vis[maxn];
int dis[maxn][maxn];
void dij(){
memset(dis,0x3f,sizeof dis);
priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > > q;
q.push(mkpr(0,mkpr(r1,c1)));
dis[r1][c1]=0;
while(!q.empty()){
auto cur=q.top().se;
q.pop();
int x=cur.fi,y=cur.se;
if(vis[x][y])continue;
vis[x][y]=1;
for(auto& v:g[x][y]){
int fx=v.fi.fi,fy=v.fi.se,w=v.se;
if(dis[fx][fy]>dis[x][y]+w){
dis[fx][fy]=dis[x][y]+w;
q.push(mkpr(dis[fx][fy],mkpr(fx,fy)));
}
}
}
if(dis[r2][c2]>1e8){
puts("-1");
return;
}
printf("%d\n",dis[r2][c2]);
}
void solve(int id_of_test){
scanf("%d%d",&n,&m);
FOR(i,1,n){
scanf("%s",s[i]+1);
}
read(r1);
read(c1);
read(r2);
read(c2);
FOR(i,1,n){
int lst=1;
FOR(j,1,m){
if(s[i][j]=='#')lst=j;
else r_lstblk[i][j]=lst;
}
lst=m;
REP(j,m,1){
if(s[i][j]=='#')lst=j;
else r_nxtblk[i][j]=lst;
}
}
FOR(j,1,m){
int lst=1;
FOR(i,1,n){
if(s[i][j]=='#')lst=i;
else c_lstblk[i][j]=lst;
}
lst=n;
REP(i,n,1){
if(s[i][j]=='#')lst=i;
else c_nxtblk[i][j]=lst;
}
}
FOR(i,1,n){
FOR(j,1,m){
if(s[i][j]=='#')continue;
if(s[i][j-1]!='#'){
g[i][j].eb(mkpr(mkpr(i,j-1),2));
}
if(s[i][j+1]!='#'){
g[i][j].eb(mkpr(mkpr(i,j+1),2));
}
if(s[i-1][j]!='#'){
g[i][j].eb(mkpr(mkpr(i-1,j),2));
}
if(s[i+1][j]!='#'){
g[i][j].eb(mkpr(mkpr(i+1,j),2));
}
}
}
FOR(i,1,n){
FOR(j,1,m){
if(s[i][j]=='#')continue;
{
int lst=c_lstblk[i][j]+1;
g[i][j].eb(mkpr(mkpr(lst,j),1));
}
{
int nxt=c_nxtblk[i][j]-1;
g[i][j].eb(mkpr(mkpr(nxt,j),1));
}
{
int lst=r_lstblk[i][j]+1;
g[i][j].eb(mkpr(mkpr(i,lst),1));
}
{
int nxt=r_nxtblk[i][j]-1;
g[i][j].eb(mkpr(mkpr(i,nxt),1));
}
}
}
dij();
}
int main()
{
int T;
T=1;
FOR(_,1,T){
solve(_);
}
return 0;
}
/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法匹配？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*/