DFS习题(二)

DFS习题(二)

题目一

#include <bits/stdc++.h>
using namespace std;

int w,h;
const int N = 25;
char a[25][25];
int st[N][N];

int max = 0;
int u[4] = {1,0,-1,0};
int d[4] = {0,1,0,-1};
int k = 1;
void dfs(int x,int y) {
    st[x][y] = 1;
    for (int i = 0;i < 4;i++) {
        int n_x = x + u[i];
        int n_y = y + d[i];
        if (a[n_x][n_y] == '.' && !st[n_x][n_y]) {
            k++;
            st[n_x][n_y] = 1;
            dfs(n_x,n_y);
        }
    }
}
int main () {
    cin >> w >> h;
    int st_x,st_y;
    for (int i = 1;i <= h;i++) {
        for (int j = 1;j <= w;j++) {
            cin >> a[i][j];
            if (a[i][j] == '@') {
                st_x = i;
                st_y = j;
            }
        }
    }
    dfs(st_x,st_y);
    cout << k;
}

题目二

#include <bits/stdc++.h>
using namespace std;

int n,m;
const int N = 110;
char a[N][N];
int st[N][N];

int res;
int dx[] = {1,0,-1,0,1,-1,1,-1};
int dy[] = {0,1,0,-1,1,1,-1,-1};

void dfs(int x,int y) {
    for (int i = 0;i < 8;i++) {
        int nx = x+dx[i];
        int ny = y+dy[i];
        if (st[nx][ny]) continue;
        if (a[nx][ny] == '.') continue;
        if (nx < 1 || nx > n || ny <1 || ny > m) continue;
        st[nx][ny] = 1;
        dfs(nx,ny);
    }
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (!st[i][j] && a[i][j] == 'W') {
                st[i][j] = 1;
                dfs(i,j);
                res++;
            }
        }
    }
    cout << res;
}

题目三

#include <bits/stdc++.h>
using namespace std;

int n,k;
int res;
void dfs(int x,int y,int sum) {
    if (sum == n && y == k) res++;
    if (x >= n) return;
    if (y >= k) return;
    for (int i = x;sum+i*(k-y) <= n;i++) {
        dfs(i,y+1,sum+i);
    }
}
int main () {
    cin >> n >> k;
    for (int i = 1;i <= n/k;i++) {
        dfs(i,1,i);
    }
    cout << res;
}