dfs

http://poj.org/problem?id=1321
入门放棋子问题

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define mp make_pair
#define ph push
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef pair<int, int> pii;
char m[10][10];
int vis[10];
int ans = 0;
int n, k;
void dfs(int x, int num) {
    if (num >= k) {
        ans++;
        return;
    }
    for (int i = x; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
           //vis 用来判断当前列是否被放过棋子
            if (m[i][j] == '#' && !vis[j]) {
                vis[j] = 1;
                dfs(i + 1, num + 1);
                vis[j] = 0;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    while (cin >> n >> k) {
        if (n == -1 && k == -1) {
            break;
        }
        memset(vis, 0, sizeof(vis));
        memset(m, 0, sizeof(m));
        for (int i = 0; i < n; ++i) {
            cin >> m[i];
        }
        ans = 0;
        dfs(0, 0);
        cout << ans << endl;
    }
    return 0;
}

https://www.luogu.org/problemnew/show/P1433

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cstring>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define ph push
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
#define all(x) (x).begin(), (x).end()
const int N = 20;
const int INF = 1e9 + 5;
int n;
double ans = INF;
pdd a[20];
int f[N];
void dfs(pdd p, int num, double sum) {
    if (sum > ans) {
        return;
    }
    if (num >= n) {
        ans = min(ans, sum);
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (!f[i]) {
            f[i] = 1;
            dfs(a[i], num + 1,
                sum + (double) sqrt((p.ff - a[i].ff) * (p.ff - a[i].ff) + (p.ss - a[i].ss) * (p.ss - a[i].ss)));
            f[i] = 0;
        }
    }
}
int main() {
//    ios::sync_with_stdio(false);
    cin >> n;
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; ++i) {
        cin >> a[i].ff >> a[i].ss;
    }
    dfs(mp(0,0), 0, 0);
    printf("%.2f\n",ans);
    return 0;
}