搜索（題目）

A.POJ_1321
考查DFS的一個循環中遞歸調用

?

?

?

?

#include<iostream>
#include<cstring>

using namespace std;
char a[10][10];     //記錄棋盤位置
int book[10];        //記錄一列是否已經放過棋子
int n, k;                // k 為 需要放入的棋子數
int total, m;    //total 是放棋子的方案數 ，m是已放入棋盤的棋子數目

void DFS(int cur)
{
    if (k == m)    {
        total++;
        return;
    }
    if (cur >= n)    //邊界
        return;
    for (int j = 0; j < n; j++)
        if (book[j] == 0 && a[cur][j] == '#'){   //判斷條件（為#才能在該處下棋）
            book[j] = 1;           //標記
            m++;
            DFS(cur + 1);            //到下一行
            book[j] = 0;           //改回來方便下一行的判斷
            m--;
        }
    DFS(cur + 1);                //到下一行
}

int main()
{
    int i;
    while ((cin >> n >> k) && n != -1 && k != -1){
        total = 0;
        m = 0;
        for (i = 0; i < n; i++)
            cin >> a[i];
        // 以上內容都是輸入
        memset(book, 0, sizeof(book));        // 對于每一組處理完了數據進行數組的清空
        DFS(0);                              // 進行搜索
        cout << total << endl;
    }
    return 0;
}

?

?B.POJ_2251

PS：六個方向的BFS題

?

?

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
//bfs對于每一層的搜索都是很詳細的可以掃完所有
using namespace std;

char map[35][35][35];    //    用于建圖
int vis[35][35][35];    // 查詢數組 判斷該點是否被訪問了
int k, n, m, sx, sy, sz, ex, ey, ez;        //k , n, m,題干要求量； sx, sy, sz,開始坐標值；ex, ey, ez終點坐標值
int to[6][3] = { {1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1} }; // 方向向量坐標
// 前后左右上下不存在順序限制

struct node{    // 定義一個結構體
    int x, y, z, step;    // x,y,z 表示 node 聲明出來的點的 三個坐標的值 和 該點下的是第幾步
};

int check(int x, int y, int z){
    // 若 1.越界 2.是障礙物 3.查詢過 該函數的返回值是 1 否則 則是 0；
    if (x < 0 || y < 0 || z < 0 || x >= k || y >= n || z >= m)
        return 1;
    else if (map[x][y][z] == '#')
        return 1;
    else if (vis[x][y][z])
        return 1;
    return 0;
}

int bfs(){
    int i;
    node a, next;
    queue<node> Q;
    a.x = sx, a.y = sy, a.z = sz;    //    從起點開始掃
    a.step = 0;
    vis[sx][sy][sz] = 1;
    Q.push(a);    // 把元素壓入隊列中
    while (!Q.empty()){    //    如果隊列q為空就證明沒找到可以通過的路徑
        a = Q.front();    // 取出隊列第一個元素
        Q.pop();    //    刪去靠前元素
        if (a.x == ex && a.y == ey && a.z == ez)
            return a.step;    //    如果掃到的該點與目標點相同則返回該點對應的步數
        for (i = 0; i < 6; i++){
            cout << "a";
            cout << a.x << a.y << a.z << endl;
            next = a;
            next.x = a.x + to[i][0];
            next.y = a.y + to[i][1];
            next.z = a.z + to[i][2];
            // 通過方向向量值改變
            cout << "next";
            cout << next.x << next.y << next.z << endl;
            if (check(next.x, next.y, next.z))
                continue;    // 如果下一步的點不和規范就不執行下面步驟
            cout << "標記next";
            cout << next.x << next.y << next.z << endl;
            vis[next.x][next.y][next.z] = 1;
            next.step = a.step + 1;
            Q.push(next);
        }
    }
    return 0;
}

int main(){
    int i, j, r;
    while (cin >> k >> n >> m, n + m + k){    // k為牢房個數n，m代表n行m列
        for (i = 0; i < k; i++){
            for (j = 0; j < n; j++){
                cin >> map[i][j];    //    建圖
                for (r = 0; r < m; r++){    // 掃一遍圖 找出起點與終點
                    if (map[i][j][r] == 'S'){
                        sx = i, sy = j, sz = r;
                    }
                    else if (map[i][j][r] == 'E'){
                        ex = i, ey = j, ez = r;
                    }
                }
            }
        }
        memset(vis, 0, sizeof(vis));
        int ans;
        ans = bfs();
        if (ans)
            cout << "Escaped in " << ans << " minute(s)." << endl;
        else
            cout << "Trapped!" << endl;
    }
    return 0;
}

?