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