Contents
Problem
找所有 1 到 3 的最短距離，其中最長的。也就是每一個 1 找離它最近的 3 ，在這之中找一個 1 ，它離 3 的距離是最遠的。
Solution
兩種作法:
一種是直接對每個 1 做 BFS 找離其最近的 3。速度較慢。
一種則是記錄下每個 1 和 3 的位置，去找它們相互間的距離。這裡可直接 $O(n^2)$ 去找每個 1 對 3 的最短距離。
或是先將 3 的位置依 x 或 y 軸做排序，接著對每個 1 用二分搜找大於等於 1 的 3。
從找到的這個 3 ，向右和向左分別做類似掃描線的手法，找出離 1 較近的 3 。雖然一樣是 $O(n^2)$ 但實際上效率會比較好。
最後都是在所有 1 的最短路徑裡找最長的。
Code
$O(n^2)$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
66
67
68
69
70
71
72
73
74
75
using namespace std;
typedef pair<int, int> Pair;
inline int dir(Pair& a, Pair& b);
inline bool cmp(const Pair& a, const Pair& b){ return a.second < b.second; }
int main()
{
int n, i, j;
Pair one[N], three[N];
while (scanf("%d", &n) != EOF)
{
getchar();
int s = 0, t = 0;
char c;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
c = getchar();
if (c == '1')
one[s].first = i, one[s++].second = j;
else if (c == '3')
three[t].first = i, three[t++].second = j;
}
getchar();
}
int max = 0;
sort(three, three + t, cmp);
for (i = 0; i < s; i++)
{
//二分搜找大於等於 one[i].second 的 three[]
int idx = lower_bound(three, three + t, one[i], cmp) - three, d = 1e9;
//往右找
for (j = idx; j < t; j++)
{
if (one[i].second + d < three[j].second)
break;
int temp = dir(three[j], one[i]);
if (temp < d)
d = temp;
}
//往左找
for (j = idx - 1; j >= 0; j--)
{
if (one[i].second - d > three[j].second)
break;
int temp = dir(three[j], one[i]);
if (temp < d)
d = temp;
}
if (d > max)
max = d;
}
printf("%d\n", max);
}
return 0;
}
int dir(Pair& a, Pair& b)
{
return abs(a.first - b.first) + abs(a.second - b.second);
}
BFS1
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
typedef pair<int, int> Pair;
bool isVisit[N][N];
char grid[N][N];
int BFS(int i, int j);
const int dir[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
int main()
{
int n, i, j;
Pair one[10000];
while (scanf("%d", &n) != EOF)
{
getchar();
//init border
for (i = 0; i <= n + 1; i++)
grid[0][i] = grid[i][0] = grid[n + 1][i] = grid[i][n + 1] = '\0';
int s = 0;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
grid[i][j] = getchar();
if (grid[i][j] == '1')
one[s].first = i, one[s++].second = j;
}
getchar();
}
int max = 0,temp;
for (i = 0; i < s; i++)
{
temp = BFS(one[i].first, one[i].second);
if (temp > max)
max = temp;
for (int k = 0; k <= n + 1; k++)
for (j = 0; j <= n + 1; j++)
isVisit[k][j] = false;
}
printf("%d\n", max);
}
return 0;
}
int BFS(int i, int j)
{
queue<Pair> Q;
Pair now = { i, j };
int dis[N][N] = {};
Q.push(now);
while (!Q.empty())
{
now = Q.front();
Q.pop();
for (int i = 0; i < 4; i++)
{
Pair next = { now.first + dir[i][0], now.second + dir[i][1] };
if (grid[next.first][next.second] && !isVisit[next.first][next.second])
{
dis[next.first][next.second] = dis[now.first][now.second] + 1;
if (grid[next.first][next.second] == '3')
return dis[next.first][next.second];
isVisit[next.first][next.second] = true;
Q.push(next);
}
}
}
return 0;
}