CF1063B Labyrinth
題意：
你正在玩一款電腦游戲，在其中一關，你位于一個 n 行 m 列的迷宮，每個格子要么是可以通過的空地，要么是障礙，迷宮的起點位于第 r 行第 c 列，你每一步可以向上、下、左、右中的一個方向移動一格，前提是那一格不是障礙，你無法越出迷宮的邊界，
不幸的是，你的鍵盤快壞了，所以你只能向左移動不超過 x 格，并且向右移動不超過 y 格，因為上下鍵情況良好，所以對向上和向下的移動次數沒有限制，
現在你想知道在滿足上述條件的情況下，從起點出發，有多少格子可以到達（包括起點）？
題解：
直接bfs+佇列搜，但是如果你對于被加入佇列的點不再二次加入，那你就會在第40個點wa住，因為有些點pos你雖然已經到達了，但是有可能還有其他的到達方法，使得到達后剩余的左右次數更多，可以去往其他更多的點，就會漏到情況，為了避免這種情況，我們用pair<int,int>sum來記錄每個坐標剩余的左右次數，初始值為-1，如果再次到達這個點時，剩余的左右次數有一個更多，說明有可能比上次可以去更遠的地方，就入站，并更新sum
本質就是bfs+剪枝
詳細看代碼
代碼：
#include <bits/stdc++.h>
#include <unordered_map>
#define debug(a, b) printf("%s = %d\n", a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll= 1e18;
const int INF_int= 0x3f3f3f3f;
void read(){};
template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar)
{
x= 0;
char c= getchar();
bool flag= 0;
while (c < '0' || c > '9')
flag|= (c == '-'), c= getchar();
while (c >= '0' && c <= '9')
x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();
if (flag)
x= -x;
read(Ar...);
}
template <typename T> inline void write(T x)
{
if (x < 0) {
x= ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#else
startTime = clock ();
freopen("data.in", "r", stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#else
endTime= clock();
printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn=2e3+9;
struct node{
int x,y;
int L,R;
};
queue<node>q;
char a[maxn][maxn];
bool b[maxn][maxn];
int dx[]={0,-1,1,0,0};
int dy[]={0,0,0,-1,1};
int n,m;
int ans=0;
PII sum[maxn][maxn];
void dfs(int x,int y,int L,int R){
q.push({x,y,L,R});
sum[x][y].first=L;
sum[x][y].second=R;
while(!q.empty()){
node p=q.front();
q.pop();
int x=p.x;
int y=p.y;
int L=p.L;
int R=p.R;
// if(b[x][y])continue;
// printf("x=%d y=%d\n",x,y);
b[x][y]=1;
for(int i=1;i<=4;i++){
int X=x+dx[i];
int Y=y+dy[i];
// if(b[X][Y])continue;
if(a[X][Y]=='*')continue;
if(X<1||X>n||Y<1||Y>m)continue;
if(i==3&&L==0)continue;
else if(i==3)L--;
if(i==4&&R==0)continue;
else if(i==4)R--;
if(sum[X][Y].first<L||sum[X][Y].second<R){
q.push({X,Y,L,R});
if(sum[X][Y].first<L)
sum[X][Y].first=L;
if(sum[X][Y].second<R)
sum[X][Y].second=R;
}
if(i==3)L++;
if(i==4)R++;
}
}
}
int main()
{
//rd_test();
read(n,m);
int r,c;
read(r,c);
int x,y;
read(x,y);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%c",&a[i][j]);
sum[i][j].first=-1;
sum[i][j].second=-1;
}
char ch=getchar();
}
dfs(r,c,x,y);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
if(b[i][j])ans++;
}
cout<<ans;
//Time_test();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/338204.html
標籤：其他