code1083免費版，[ CodeForces 1063 B ] Labyrinth

\(\\\)

\(Description\)

---

給出一個四聯通的\(N\times M\) 網格圖和起點。圖中有一些位置是障礙物。

code1083免費版。現在上下移動步數不限，向左至多走 \(a\) 步，向右至多走 \(b\) 步，求從起點出發能到達多少個空地。

• \(N,M\le 2000\)

\(\\\)

\(Solution\)

---

爺們太神了......

開始的想法是直接跑最短路， \(dist\) 為橫向移動總步數。

后來發現矛盾在于，如果到一個格子向左走的步數較少，向右走的步數較多，和這種情況反過來，無法確定那種更優，進而無法確定用那種狀態更新接下來的點。

然后聽爺們講了好久聽懂了正確性證明。考慮要從起點 U 到達 V 這個格子，它橫向的差值為 \(2\) 是固定的。

也就是說，任何一個合法的方案向左走的步數減掉向右走的步數都應該等于 \(2\)。

那么這種矛盾不存在了。因為向左向右的步數會同時增長，否則一定不會到達這個目標點。

然后就愉快上最短路，根據\(Dij\) 的原理，循環次數就是訪問的點數。

\(\\\)

\(Code\)

---

#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 2010
#define R register
#define gc getchar
#define inf 2000000000
using namespace std;
typedef long long ll;inline ll rd(){ll x=0; bool f=0; char c=gc();while(!isdigit(c)){if(c=='-')f=1;c=gc();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}return f?-x:x;
}int n,m,lx,rx,ux,uy,ans;bool mp[N][N],vis[N][N];struct dist{int x,y,l,r,sum;friend operator < (const dist &x,const dist &y){return x.sum>y.sum;}
}dis[N][N];priority_queue<dist> q;int main(){n=rd(); m=rd();ux=rd(); uy=rd();lx=rd(); rx=rd();char c=gc();for(R int i=1;i<=n;++i)for(R int j=1;j<=m;++j){while(c!='.'&&c!='*') c=gc();mp[i][j]=(c=='.');c=gc();dis[i][j].x=i; dis[i][j].y=j;dis[i][j].l=dis[i][j].r=dis[i][j].sum=inf;}dis[ux][uy].l=dis[ux][uy].r=dis[ux][uy].sum=0;q.push(dis[ux][uy]);while(!q.empty()){dist x=q.top(); q.pop();if(vis[x.x][x.y]) continue;vis[x.x][x.y]=1; ++ans;if(mp[x.x+1][x.y]){if(dis[x.x+1][x.y].sum>x.sum){dis[x.x+1][x.y].l=x.l;dis[x.x+1][x.y].r=x.r;dis[x.x+1][x.y].sum=x.sum;q.push(dis[x.x+1][x.y]);}}if(mp[x.x-1][x.y]){if(dis[x.x-1][x.y].sum>x.sum){dis[x.x-1][x.y].l=x.l;dis[x.x-1][x.y].r=x.r;dis[x.x-1][x.y].sum=x.sum;q.push(dis[x.x-1][x.y]);}}if(mp[x.x][x.y-1]&&x.l<lx){if(dis[x.x][x.y-1].sum>x.sum+1){dis[x.x][x.y-1].l=x.l+1;dis[x.x][x.y-1].r=x.r;dis[x.x][x.y-1].sum=x.sum+1;q.push(dis[x.x][x.y-1]);}}if(mp[x.x][x.y+1]&&x.r<rx){if(dis[x.x][x.y+1].sum>x.sum+1){dis[x.x][x.y+1].l=x.l;dis[x.x][x.y+1].r=x.r+1;dis[x.x][x.y+1].sum=x.sum+1;q.push(dis[x.x][x.y+1]);}}}printf("%d\n",ans);return 0;
}