CF 1064 D. Labyrinth

D. Labyrinth

http://codeforces.com/contest/1064/problem/D

题意：

　　n*m的矩阵，只能往左走l次，往右走r次，上下走无限制，问能走到多少个点。

分析：

　　01bfs。

　　直接bfs会出现问题，因为一旦打上标记后，下一次无法访问到，但是下一次的状态还更优。

像这样的样例：

.....
.***.
...*.
*.**.
*.**.
*....

做法：用双端队列，向上走或向下走时就push到队头，向左走或向右走时就push到队尾（其实就是先处理一列）。这样我们就能保证给某个格子打上标记时，当前剩余的向左走和向右走的次数是最多这样我们就能保证给某个格子打上标记时，当前剩余的向左走和向右走的次数是最多的啦。

引用自：dummyummy

0-1BFS用来解决：边权值为0或1，或者能够转化为这种边权值的最短路问题，时间复杂度为O(E+V).

0-1BFS,从队列front中去除点u，遍历u的所有边，如果当前边可以进行relax操作，则relax，然后判断level，若level相同，放到队列的front，否则，放到back，队列采用双端队列deque。

实际上跟最短路挺像。另外：由于松弛操作的存在，0-1bfs可以去掉vis数组，而且速度会更快。

引用自：R灬O灬J

代码：

 1 /*
 2 * @Author: mjt
 3 * @Date:   2018-10-16 21:52:39
 4 * @Last Modified by:   mjt
 5 * @Last Modified time: 2018-10-16 23:03:39
 6 */
 7 #include<cstdio>
 8 #include<algorithm>
 9 #include<cstring>
10 #include<cmath>
11 #include<iostream>
12 #include<cctype>
13 #include<set>
14 #include<vector>
15 #include<queue>
16 #include<map>
17 #define fi(s) freopen(s,"r",stdin);
18 #define fo(s) freopen(s,"w",stdout);
19 using namespace std;
20 typedef long long LL;
21 
22 inline int read() {
23     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
24     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
25 }
26 
27 const int N = 2005;
28 
29 struct Node{
30     int x, y, l, r;
31     Node() {}
32     Node(int _1,int _2,int _3,int _4) { x = _1, y = _2, l = _3, r = _4; }
33 };
34 
35 int n, m, sx, sy, L, R;
36 bool vis[N][N];
37 char s[N][N];
38 deque <Node> q;
39 
40 int dx[10] = {1, -1, 0, 0};
41 int dy[10] = {0, 0, 1, -1};
42 
43 void bfs() {
44     vis[sx][sy] = 1;
45     q.push_front(Node(sx, sy, L, R));
46     while (!q.empty()) {
47         Node now = q.front(); q.pop_front();
48         for (int i=0; i<4; ++i) {
49             int x = now.x + dx[i], y = now.y + dy[i];
50             if (x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && s[x][y] == '.') {
51                 if (i == 0 || i == 1) vis[x][y] = 1, q.push_front(Node(x, y, now.l, now.r)); // vis的位置！！！ 
52                 else if (i == 2 && now.r) vis[x][y] = 1, q.push_back(Node(x, y, now.l, now.r - 1));
53                 else if (i == 3 && now.l) vis[x][y] = 1, q.push_back(Node(x, y, now.l - 1, now.r));
54             }
55         }
56     }
57 }
58 int main() {
59     n = read(), m = read(), sx = read(), sy = read(), L = read(), R = read();
60     for (int i=1; i<=n; ++i) scanf("%s", s[i] + 1);
61     bfs();
62     int ans = 0;
63     for (int i=1; i<=n; ++i)
64         for (int j=1; j<=m; ++j) ans += vis[i][j];
65     cout << ans;
66     return 0;
67 }