链接: https://ac.nowcoder.com/acm/contest/332/J
题意:
你在一个 n 行 m 列的网格迷宫中, 迷宫的每一格要么为空, 要么有一个障碍.
你当前在第 r 行第 c 列 (保证该格子为空). 每次移动你可以向上下左右任意一个方向移动一格, 前提是不能走到障碍上, 也不能超出迷宫的边界.
你向左移动的次数不能超过 x 次, 向右不能超过 y 次.
问在这种情况下, 对于每个格子, 是否存在一种移动方案让你走到它.
输出有多少个格子存在移动方案让你走到它.
思路:
BFS 题目数据有点弱, 普通 bfs 都过了.
看博客找到一份 hack 代码.
改了一下, 感觉还是有点问题.
Vis 数组记录到某个点的左右剩余次数, 当新过去的点剩余次数大于旧的, 就更新一下, 解决因为 bfs 顺序引起的问题.
代码:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int MAXN = 1e3 + 10;
- int Next[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
- struct Node
- {
- int _x;
- int _y;
- int _l;
- int _r;
- Node(int x, int y, int l, int r):_x(x), _y(y), _l(l), _r(r){}
- };
- char Map[MAXN][MAXN];
- int Vis[MAXN][MAXN][2];
- int n, m, sx, sy;
- int l, r;
- int main()
- {
- cin>> n>> m;
- cin>> sx>> sy;
- cin>> l>> r;
- for (int i = 1;i <= n;i++)
- {
- for (int j = 1;j <= m;j++)
- cin>> Map[i][j];
- }
- queue<Node> que;
- que.emplace(sx,sy,l,r);
- Map[sx][sy] = '+';
- Vis[sx][sy][0] = l;
- Vis[sx][sy][1] = r;
- while (!que.empty())
- {
- Node now = que.front();
- for (int i = 0;i <4;i++)
- {
- int tx = now._x + Next[i][0];
- int ty = now._y + Next[i][1];
- if (tx < 1 || tx> n || ty <1 || ty> m)
- continue;
- if (Map[tx][ty] == '*')
- continue;
- if (i == 1)
- {
- if (now._r == 0)
- continue;
- Map[tx][ty] = '+';
- if (Vis[now._x][now._y][0]> Vis[tx][ty][0] || Vis[now._x][now._y][1]> Vis[tx][ty][1])
- {
- que.emplace(tx, ty, now._l, now._r - 1);
- Vis[tx][ty][0] = Vis[now._x][now._y][0];
- Vis[tx][ty][1] = Vis[now._x][now._y][1] - 1;
- }
- }
- else if (i == 3)
- {
- if (now._l == 0)
- continue;
- Map[tx][ty] = '+';
- if (Vis[now._x][now._y][0]> Vis[tx][ty][0] || Vis[now._x][now._y][1]> Vis[tx][ty][1])
- {
- que.emplace(tx, ty, now._l - 1, now._r);
- Vis[tx][ty][0] = Vis[now._x][now._y][0] - 1;
- Vis[tx][ty][1] = Vis[now._x][now._y][1];
- }
- }
- else
- {
- Map[tx][ty] = '+';
- if (Vis[now._x][now._y][0]> Vis[tx][ty][0] || Vis[now._x][now._y][1]> Vis[tx][ty][1])
- {
- que.emplace(tx, ty, now._l, now._r);
- Vis[tx][ty][0] = Vis[now._x][now._y][0];
- Vis[tx][ty][1] = Vis[now._x][now._y][1];
- }
- }
- }
- que.pop();
- }
- int res = 0;
- for (int i = 1;i <= n;i++)
- for (int j = 1;j <= m;j++)
- if (Map[i][j] == '+')
- res++;
- /*
- for (int i = 1;i <= n;i++)
- {
- for (int j = 1;j <= m;j++)
- cout << Map[i][j];
- cout << endl;
- }
- */
- cout << res << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945451.html