Artwork (Gym - 102346A)
題目鏈接
演算法
DFS，連通塊
時間復雜度：O(k*n + k * k)
1.這道題就是讓你判斷從(0,0)到(m,n)，避開中途所有的傳感器(傳感器的檢測范圍為半徑為s的圓)的檢測區域，最終能否到達(m,n)，
2.這道題很容易想到圓與圓相切或相交最后把能出去的路全堵上了，具體是把上下、左右、左下、右上這四個邊界給堵掉一部分(只要滿足前面四種情況的其中一個，就過不去)，見下圖，
很明顯，這樣堵絕對出不去，然而方法是有，但怎么實作它呢？由于當時以為這是個復雜的計算幾何的題，結果看了半天計算幾何模板卻無從下手(其實只涉及了一點計算幾何的知識，就是判斷兩個圓是否相交或相切)，最終未果，查閱了一些解題博客后了解到該題可以用DFS,連通塊的思想來實作，當然還有是用并查集實作，不過并沒有看并查集是怎么實作它的，這里先只介紹如何用DFS來實作它，
3.首先應明確一點，就是如何判斷兩圓是否相交或相切，即圓心之間的距離要大于等于半徑之和，
d = sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2))
d >= r1 + r2
為了避免sqrt后影響精度,故兩邊都開平方
d*d >= (r1 + r2)*(r1 + r2)
即(x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) >= (r1 + r2)*(r1 + r2)
4.如果兩個圓相交或相切，我們可以就把它們視為一體，這樣就構成了一個連通塊，判斷連通塊是否滿足上面四個條件，至于如何判斷，就是判斷連通塊中的每個圓是否觸及邊界，具體用下列式子來判斷，
x - r <= 0 --> 觸及左邊界
x + r >= m --> 觸及右邊界
y - r <= 0 --> 觸及下邊界
y + r >= n --> 觸及上邊界
5.好了，現在知道怎么判斷是否觸及邊界了，那么就需要想一下怎么知道連通塊中包含哪些圓呢？這里我們可以借助圖論的相關知識，就是如果兩個圓有接觸，就在這兩個圓之間建立一條連接，我們可以把這個圓抽象成一個節點，這就變成了在兩個節點之間建立一條無向邊，這個連通塊就成了一個圖，遍歷這個圖即可知道這個連通塊包含哪些圓，
6.大致的實作思路有了，現在我們來看如何用代碼實作，
C++代碼
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = 2e6 + 10; //注意M要取到N*N,原因是其中一個圓可能和其他所有圓都相交或相切
int m, n, k;
struct Sensor{
int x, y, s;
}sen[N];
int h[N], e[M], ne[M], idx;
bool st[5]; //0,1,2,3分別代表上下左右四個邊界是否接觸
bool vis[N]; //該圓是否被訪問過
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//判斷兩圓是否相交或相切
bool check(Sensor a, Sensor b)
{
if((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) <= (a.s + b.s) * (a.s + b.s)) return true;
return false;
}
void dfs(int u)
{
vis[u] = true;
int x = sen[u].x, y = sen[u].y, s = sen[u].s;
if(x - s <= 0) st[2] = true;
if(x + s >= m) st[3] = true;
if(y - s <= 0) st[1] = true;
if(y + s >= n) st[0] = true;
//遍歷與該圓連通的圓
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!vis[j])
dfs(j);
}
}
int main()
{
cin >> m >> n >> k;
memset(h, -1, sizeof h);
for(int i = 0; i < k; i++)
cin >> sen[i].x >> sen[i].y >> sen[i].s;
for(int i = 0; i < k; i++)
for(int j = i + 1;j < k; j++)
{
if(check(sen[i], sen[j]))
{
add(i, j);
add(j, i);
}
}
bool flag = false;
for(int i = 0; i < k; i++)
{
if(flag) break;
if(vis[i]) continue;
memset(st, 0, sizeof st);
dfs(i);
if((st[0] || st[2]) && (st[1] || st[3]))
flag = true;
}
if(flag)
puts("N");
else
puts("S");
}
此代碼中使用的用鄰接表建立圖來源于yxc大佬的模板
解題思路來源
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/140494.html
標籤：其他