Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator