健身器材网站源码,网站专业术语中 seo意思是,那家网站做照片书好,广告公司企业网站模板CF1063B Labyrinth
题意#xff1a;
你正在玩一款电脑游戏。在其中一关#xff0c;你位于一个 n 行 m 列的迷宫。每个格子要么是可以通过的空地#xff0c;要么是障碍。迷宫的起点位于第 r 行第 c 列。你每一步可以向上、下、左、右中的一个方向移动一格#xff0c;前提是…CF1063B Labyrinth
题意
你正在玩一款电脑游戏。在其中一关你位于一个 n 行 m 列的迷宫。每个格子要么是可以通过的空地要么是障碍。迷宫的起点位于第 r 行第 c 列。你每一步可以向上、下、左、右中的一个方向移动一格前提是那一格不是障碍。你无法越出迷宫的边界。
不幸的是你的键盘快坏了所以你只能向左移动不超过 x 格并且向右移动不超过 y 格。因为上下键情况良好所以对向上和向下的移动次数没有限制。
现在你想知道在满足上述条件的情况下从起点出发有多少格子可以到达包括起点
题解
直接bfs队列搜但是如果你对于被加入队列的点不再二次加入那你就会在第40个点wa住因为有些点pos你虽然已经到达了但是有可能还有其他的到达方法使得到达后剩余的左右次数更多可以去往其他更多的点就会漏到情况。为了避免这种情况我们用pairint,intsum来记录每个坐标剩余的左右次数初始值为-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 pairint, 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
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn2e39;
struct node{int x,y;int L,R;
};
queuenodeq;
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 ans0;
PII sum[maxn][maxn];
void dfs(int x,int y,int L,int R){q.push({x,y,L,R});sum[x][y].firstL;sum[x][y].secondR;while(!q.empty()){node pq.front();q.pop();int xp.x;int yp.y;int Lp.L;int Rp.R;
// if(b[x][y])continue;
// printf(x%d y%d\n,x,y);b[x][y]1;for(int i1;i4;i){int Xxdx[i];int Yydy[i];
// if(b[X][Y])continue;if(a[X][Y]*)continue;if(X1||Xn||Y1||Ym)continue;if(i3L0)continue;else if(i3)L--;if(i4R0)continue;else if(i4)R--;if(sum[X][Y].firstL||sum[X][Y].secondR){q.push({X,Y,L,R});if(sum[X][Y].firstL)sum[X][Y].firstL;if(sum[X][Y].secondR)sum[X][Y].secondR;}if(i3)L;if(i4)R; }}
}
int main()
{//rd_test();read(n,m);int r,c;read(r,c);int x,y;read(x,y);for(int i1;in;i){for(int j1;jm;j){scanf(%c,a[i][j]);sum[i][j].first-1;sum[i][j].second-1;}char chgetchar();}dfs(r,c,x,y);for(int i1;in;i){for(int j1;jm;j)if(b[i][j])ans;}coutans;//Time_test();
}
