BFS/DFS板子题

/*
title: bfs
data: 2020.10.28

1. 复习pair, queue, stack
2. 二叉树遍历
3. 模板
4. 水体讲解

*/



/*

stack & queue


empty()
pop()
push()
size()

top()
front()






stack & queue

empty() 堆栈为空则返回真
pop() 移除栈顶/队首元素
push() 在栈顶/队尾增加元素
size() 返回栈/队列中元素数目

top() 返回栈顶元素
front() 返回队首元素

*/



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

struct node {
    int x;
    int y;
};

int main() {
    int a, b, c, d;
    scanf("%d %d", &a, &b);
    scanf("%d %d", &d, &c);

    pair<int, int >q0;//定义

    pair<int, int >q1(a, b);//定义,并赋值

    pair<int, int >q2 = make_pair(d, c);//创建

    if (q1 < q2)
        printf("若p1.first < p2.first ||(p1.first = p2.first &&  p1.second < p2.second) 则p1 < p2为ture\n");
    //先比较first, 如果相同, 再去比较second

    if (q1 == q2)
        printf("pair中两个成员依此相等则为ture\n");

    return 0;
}
*/



/*

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <queue>
#include <stack>
using namespace std;

struct node {
    int x;
    int y;
};

queue<node>q;
//stack<int, int>st;

int ans;
int n, m;
char s[22][22];
bool vis[22][22];
int dir[4][2] = { 0,1,0,-1,1,0,-1,0 };

int x, y;

int judge(int x, int y) {
    if (x < 1 || x > m || y < 1 || y > n)
        return 0;
    return 1;
}


//void BFS(int x, int y) {
//    if (!judge(x, y) || s[x][y] == '#' || vis[x][y] == 1) {
//        //cout << '1';
//        return;
//    }
//    vis[x][y] = 1;
//    ans++;
//    BFS(x + 1, y);
//    BFS(x - 1, y);
//    BFS(x, y - 1);
//    BFS(x, y + 1);
//}

void BFS_() {
    node p, z;
    while (!q.empty()) {
        p = q.front();
        q.pop();
        int x = p.x;
        int y = p.y;
        if (!judge(x, y) || s[x][y] == '#' || vis[x][y] == 1) {
            continue;
        }
        vis[x][y] = 1;
        ans++;
        for (int i = 0; i <= 3; i++) {
            if (judge(x + dir[i][0], y + dir[i][1])) {
                z.x = x + dir[i][0];
                z.y = y + dir[i][1];
                q.push(z);
            }
        }
    }
}

int main() {
    while (cin >> n >> m) {
        memset(vis, 0, sizeof vis);
        ans = 0;
        getchar();
        if (n == m && n == 0)
            break;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%c", &s[i][j]);
                if (s[i][j] == '@') {
                    x = i;
                    y = j;

                    //node p;
                    //p.x = x;
                    //p.y = y;
                    //q.push(p);
                    //cout << x << y << '\n';
                }
            }
            getchar();
        }

        BFS(x, y);
        //BFS_();
        cout << ans << '\n';
    }
    return 0;
}
*/


/*

int dir[4][2] = { 0,1,0,-1,1,0,-1,0 };

int x, y;

int judge(int x, int y) {
    if (x < 1 || x > m || y < 1 || y > n)
        return 0;
    return 1;
}


void BFS_() {
    node p, z;
    while (!q.empty()) {
        p = q.front();
        q.pop();
        int x = p.x;
        int y = p.y;
        if (!judge(x, y) || s[x][y] == '#' || vis[x][y] == 1) {
            continue;
        }
        vis[x][y] = 1;
        ans++;
        for (int i = 0; i <= 3; i++) {
            if (judge(x + dir[i][0], y + dir[i][1])) {
                z.x = x + dir[i][0];
                z.y = y + dir[i][1];
                q.push(z);
            }
        }
    }
}

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.

*/


#include<iostream>
#include<cstring>
#include <stack>
using namespace std;

char map[9][9];
int vis[9];
int N, K;
int way;
int ans;

void DFS(int k) {
    if (way == K) {
        ans++;
        return;
    }
    if (k >= N)
        return;
    for (int j = 0; j < N; j++) {
        if (!vis[j] && map[k][j] == '#') {
            vis[j] = 1;
            way++;
            DFS(k + 1);
            vis[j] = 0;
            way--;
        }
    }
    DFS(k + 1);
}

int main() {
    //ios::sync_with_stdio(false);
    int i, num;
    while (cin >> N >> K) {
        if (N == -1 && K == -1)
            break;
        memset(map, 0, sizeof(map));
        memset(vis, 0, sizeof(vis));
        for (i = 0; i < N; i++) {
            cin >> map[i];
        }
        ans = way = 0;
        DFS(0);
        cout << ans << endl;
    }
    return 0;
}




//#include <bits/stdc++.h>


/*
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <queue>
#include <stack>
using namespace std;

int n, m;
char s[22][22];
int x, y;

int ans;
int vis[22][22];

int judge(int x, int y) {
    if (x < 1 || x > m || y < 1 || y > n)
        return 0;
    return 1;
}

void bfs(int x, int y) {
    if (vis[x][y] == 1 || !judge(x, y) || s[x][y] == '#')
        return;
    vis[x][y] = 1;
    ans++;
    bfs(x + 1, y);
    bfs(x - 1, y);
    bfs(x, y + 1);
    bfs(x, y - 1);
}

int main() {
    while (cin >> n >> m) {
        ans = 0;
        memset(vis, 0 ,sizeof vis);
        if (n == 0 && m == 0)
            break;
        //getchar();
        for (int i = 1; i <= m; i++) {
            scanf("%s", s[i]);
        }
            //for (int j = 1; j <= n; j++) {
            //    scanf("%c", &s[i][j]);
            //    if (s[i][j] == '@') {
            //        x = i;
            //        y = j;
            //    }
            //}
            //getchar();
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                cout << s[i][j];
            }
            cout << '\n';
        }
        //bfs(x, y);
        //cout << ans << '\n';
    }
    return 0;
}
*/