Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这题目是不是DFS会爆？

Posted by JiananYuan at 2019-12-10 09:19:18 on Problem 2236
```#include <iostream>
#include <cstring>
#define MAX 105
using namespace std;
int n,d;
int mp[MAX][MAX];
struct node {
int x,y;
bool available;
node(): available(false) {}
}a[MAX];
bool judge(const node& na,const node& nb) {
return ((na.available && nb.available) && (na.x - nb.x)*(na.x - nb.x)+(na.y - nb.y)*(na.y - nb.y) <= d*d);
}
int des;
int book[MAX];
bool dfs(int i) {
if(i == des) return true;
for(int j=1;j<=n;j++) {
if(mp[i][j] == 1 && book[j] == 0) {
book[j] = 1;
if(dfs(j)) return true;
book[j] = 0;
}
}
return false;
}
int main() {
cin >> n >> d;
for(int i=1;i<=n;i++) cin >> a[i].x >> a[i].y;
string op;
while(cin >> op) {
if(op == "O") {
int x; cin >> x;
a[x].available = true;
for(int i = 1;i <= n;i++) {
if(judge(a[x],a[i])) mp[x][i] = 1;
if(judge(a[i],a[x])) mp[i][x] = 1;
}
}
if(op == "S") {
memset(book,0,sizeof(book));
int x; cin >> x >> des;
if(dfs(x)) cout<<"SUCCESS"<<endl;
else       cout<<"FAIL"<<endl;
}
}
return 0;
}
```

Followed by: