CF1063B Labyrinth

思路：
使用bfs，不过每个点可以访问多次。
实现：
 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 typedef pair<int, int> pii;
 7 
 8 const int dx[4] = {1, 0, -1, 0};
 9 const int dy[4] = {0, 1, 0, -1};
10 const int INF = 0x3f3f3f3f;
11 
12 char a[2005][2005];
13 int n, m, r, c, L, R;
14 int d[2005][2005];
15 
16 int main()
17 {
18     while (cin >> n >> m >> r >> c >> L >> R)
19     {
20         for (int i = 0; i < n; i++)
21         {
22             for (int j = 0; j < m; j++)
23             {
24                 cin >> a[i][j];
25                 d[i][j] = INF;
26             }
27         }
28         r--; c--;
29         queue<pii> q;
30         q.push(pii(r, c));
31         d[r][c] = 0;
32         while (!q.empty())
33         {
34             pii tmp = q.front();
35             q.pop();
36             int x = tmp.first, y = tmp.second;
37             for (int i = 0; i < 4; i++)
38             {
39                 int nx = x + dx[i], ny = y + dy[i];
40                 if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == '.')
41                 {
42                     int nd = d[x][y] + (i == 3);
43                     if (nd < d[nx][ny])
44                     {
45                         q.push(pii(nx, ny));
46                         d[nx][ny] = d[x][y] + (i == 3);
47                     }
48                 }
49             }
50         }
51         int cnt = 0;
52         for (int i = 0; i < n; i++)
53         {
54             for (int j = 0; j < m; j++)
55             {
56                 if (d[i][j] <= L && d[i][j] + j - c <= R) cnt++;
57             }
58         }
59         cout << cnt << endl;
60     }
61     return 0;
62 }