BOI2013 tracks in the snow 题解

Edited on | In | Comments:

Problem

Describe

There is a rectangular meadow in a forest, having been covered with a blanket of fresh snow in themorning (left in the figure below). Rabbits and foxes, who live in the forest, are crossing the meadow and leave their tracks in the snow.

They always enter in the upper left corner and leave the meadow from the lower right corner. In between they can move back and forth, playing in the snow, even crossing their own tracks. At anytime there is at most one animal on the meadow. No animal enters the meadow more than once.

The movements of the animals can be described by dividing the meadow into quadratic cells. The animals never move diagonally in a single step and they never jump over a cell. When an animal enters a cell its tracks will cover all previous tracks left in this cell.
For example, first a rabbit crossed the meadow from top-left to bottom-right (middle in the figure).
After that, a fox crossed, and now his tracks are partially covering the rabbit’s (right in the figure).

1
2
3
4
5
........ RRR..... FFR.....
........ ..RRR... .FRRR...
........ ..R..... .FFFFF..
........ ..RRRR.R ..RRRFFR
........ .....RRR .....FFF

You are given a map of the meadow at some time after indicating for each cell if there are any visible tracks and whether they were left by a rabbit or by a fox (right in the figure).

You are interested in the local wildlife population. Write a program to determine the minimal possible number N of animals that must have crossed the meadow to leave the given pattern of tracks in the snow.

Input

The first line contains two integers H and W, the height and the width of the map of the meadow. H lines follow with exactly W characters on each: the map, where ‘.’ marks untouched snow, ‘R’ a spot where a rabbit’s track is the topmost one, and ‘F’ a spot where a fox’s track is the topmost one. There is at least one track on the meadow.

Output

The output should consist of a single integer: the minimal number N ≥ 1 of animals that could have left the tracks given in the input.

Constraints

1 ≤ H, W ≤ 4000
In test cases worth 30 points: N ≤ 200 and H, W ≤ 500

Example

1
2
3
4
5
6
7
Input #1
5 8     
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
1
2
Output #1
2

Limits

Time limit: 2 sec per test case

Memory limit: 1300 MB per test case

Solution

注意到测试数据保证有解。

主要题干已经加粗。

暴力

标签里的BFS已经明示了这是一道搜索题。

题目里很重要的一条信息是脚印可以覆盖。

于是可以想到，如果两只动物交替走，那么后一次动物走过的地方即使上一次动物可以走的地方。

我们可以将走过的动物脚印全部都变为另外一种动物的脚印，这样下来，如果全屏只有一只动物的脚印，那么就说明不需要再有别的动物走了。

因为每一次反色都代表了一只动物走过，所以答案就是 运行次数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//TLE code
#include <bits/stdc++.h>
using namespace std;

const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
const int MAXN = 4000 + 5;
char ch;
int n, m;
int g[MAXN][MAXN];
bool Visit[MAXN][MAXN];
queue<pair<int, int> > Q;
int ans;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        ch = getchar();
        for (int j = 1; j <= m; j++)
        {
            ch = getchar();
            switch (ch)
            {
                case 'R': g[i][j] = 0;    break;
                case '.': g[i][j] = -1;   break;
                case 'F': g[i][j] = 1;    break;
            }
        }
    }
    while (true)
    {
        for (int i = 0; i <= n + 1; i++)
            for (int j = 0; j <= m + 1; j++)	
                Visit[i][j] = false;
        ans++;
        Q.push(make_pair(1, 1));
        while (!Q.empty())
        {
            pair<int, int> now = Q.front(); Q.pop();
            int x = now.first, y = now.second;
            Visit[x][y] = true;
            for (int i = 0; i < 4; i++)
            {
                int fx = x + dx[i], fy = y + dy[i];
                if (fx < 1 || fy < 1 || fx > n || fy > m || g[x][y] != g[fx][fy] || Visit[fx][fy]) continue;
                Q.push(make_pair(fx, fy));
            }
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)	
                if (Visit[i][j]) g[i][j] = 1 - g[i][j];
        bool ra = false, fo = false;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                if (g[i][j] == 0) ra = true;
                else if (g[i][j] == 1) fo = true;
            }
        if (!(ra && fo)) break;
    }
    cout << ans + 1 << endl;
    return 0;
}

交上去一看，T飞了，第二个点就跑了9s。

因此我们需要对这个算法进行一点优化

优化

之所以会TLE，对于循环退出的判断占了很大一部分。并且，我们在搜索过程中，反复经过已经走过的位置，这样效率便很低。

因为走过的部分一定可以再走，所以我们只需要考虑没走过的部分。

优化后的算法变成了“填棋盘”，即整个棋盘只走一遍，大大提高了效率。

对于循环退出的判断也优化了很多，详见代码。

（注：这份代码在本机上测最慢的点跑了将近4s，如果还有优化请在评论区回复，感谢您的贡献）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

const int dx[4] = { -1, 0, 1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
const int MAXN = 4000 + 5;
char ch;
int n, m;
bool g[MAXN][MAXN];
bool Visit[MAXN][MAXN];
queue<pair<int, int> > Q[2];
int ans;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        ch = getchar();
        for (int j = 1; j <= m; j++)
        {
            ch = getchar();
            switch (ch)
            {
                case 'R': g[i][j] = 0;    break;
                case '.': Visit[i][j] = true; break;
                case 'F': g[i][j] = 1;    break;
            }
        }
    }
    Q[0].push(make_pair(1, 1));
    Q[0].push(make_pair(n, m));
    int k = 0;
    while (!Q[k].empty())
    {
        while (!Q[k].empty())
        {
            pair<int, int> now = Q[k].front(); Q[k].pop();
            int x = now.first, y = now.second;
            if (Visit[x][y]) continue;
            Visit[x][y] = true;
            for (int i = 0; i < 4; i++)
            {
                int fx = x + dx[i], fy = y + dy[i];
                if (fx < 1 || fy < 1 || fx > n || fy > m || Visit[fx][fy]) continue;
                if (g[x][y] ^ g[fx][fy]) Q[1 - k].push(make_pair(fx, fy));
                else Q[k].push(make_pair(fx, fy));
            }
        }
        k = 1 - k; ans++;
    }
    cout << ans << endl;
    return 0;
}

Data

测试数据 提取码：3vm2