| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
这题目是不是DFS会爆?#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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator