DFS深度优先搜索练习

题目：Oil Deposits

题意：用@代表油田，八个方向互相连接，把相连的油田看作一块油田，问你最多有多少块油田。
思路：本题其实本质就是一个迷宫问题，所以我们就可以用dfs或者bfs,本题我们当然采用dfs,用一个vis标记一下，然后从头开始遍历，如果这个点等于‘@’并且vis为0时，开始bfs一次，记录bfs的次数，bfs的次数就是结果。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
char str[maxn][maxn];
int vis[maxn][maxn], n, m;
int dx[10] = {0,0,1,1,1,-1,-1,-1};
int dy[10] = {1,-1,0,-1,1,1,0,-1};
int cnt = 1;
void dfs(int x, int y)
{
    vis[x][y] = 1;//标记
    for(int i = 0; i < 8; i++)
    {
        int fx = x + dx[i];
        int fy = y + dy[i];
        if(str[fx][fy] == '@' && fx >= 0 && fx < n && fy >= 0 && fy < m && !vis[fx][fy])vis[fx][fy] = 1,dfs(fx, fy);
    }
}
int main()
{
    while(scanf("%d %d", &n, &m) && n && m)
    {
        memset(vis, 0, sizeof(vis));
        cnt = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%s", str[i]);
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(str[i][j] == '@' && !vis[i][j])
                {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

题目：棋盘问题

题意：就是给你一个棋盘形状不规则，用：‘#’代表棋盘,并且同一行或者同一列不能只能有一个棋子，问你能有多少种方法。
思路：因为本题的数据非常的小，最大也就是10，但是它告诉你答案却是非常的大，所以很容易想到dfs。如何dfs搜索，我们dfs搜索的使用用vis标记纵列，dfs搜索横列
代码：

#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn = 11;
char str[maxn][maxn];
int vis[maxn];//标记纵列
int sum , n, m, num;
void dfs(int x){
     if(num == m){//当棋子的数量等于m的时候，棋子的安排个数加1
        sum++;
        return;
     }
     if(x >= n)return;
     for(int i = 0; i < n; i++){
        if(str[x][i] == '#' && !vis[i]){
            vis[i] = 1;
            num++;
            dfs(x+1);
            vis[i] = 0;
            num--;
        }
     }
     dfs(x+1);
}
int main(){
    while(scanf("%d %d",&n, &m) && m != -1 && m != -1){
        for(int i = 0; i < n; i++)scanf("%s",str[i]);
        memset(vis, 0, sizeof(vis));
        num = 0;
        sum = 0;
        dfs(0);
        printf("%d\n", sum);
    }
return 0;
}

题目：N皇后问题

题意：在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
思路：本题跟上面的题型差不多，只不过在搜索的时候增加判断语句，不允许处在与棋盘边框成45角的斜线上，所以需要再增加一个判断。但是此题存在一个问题就是是多组数据输入，所以需要打表，因为就存在1~10中情况，所以需要预处理。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 11;
int vis[maxn], record[maxn];
int res[maxn], ans, n;
bool check(int x1, int y1, int x2, int y2)//判断是否在棋盘边框成45角的斜线上
{
    if((x1-y1 == x2-y2)||(x1+y1 == x2+y2))return true;
    else return false;
}
void dfs(int pos)//以横坐标深搜
{
    if(pos == n)
    {
        ans ++;
        return;
    }
    int flag;
    for(int i = 0; i < n; i++)
    {
        if(!vis[i])//纵坐标没有标记所
        {
            flag = 0;
            for(int j = 0; j < pos; j++)//判断是否在棋盘边框成45角的斜线上
            {
                if(check(pos,i, j, record[j]))
                {
                    flag = 1;
                    break;
                }
            }
            if(!flag)//不再在棋盘边框成45角的斜线上
            {
                vis[i] = 1;//标记一下
                record[pos] = i;
                dfs(pos+1);
                vis[i] = 0;//恢复现场
                record[pos] = 0;
            }
        }
    }

}

int main()
{
    for(int i = 1; i <= 10; i++)
    {
        n = i;
        ans = 0;
        dfs(0);
        res[i] = ans;
    }
    while(scanf("%d", &n),n != 0)
    {
        printf("%d\n", res[n]);
    }


    return 0;
}

题目：Knight’s Journey

代码：

#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn  = 100;
int vis[maxn][maxn], path[maxn][maxn];

int dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2};

int p, q, flag = 0;;
void dfs(int x, int y, int step)
{
    path[step][0] = x;
    path[step][1] = y;
    if(step == p*q)
    {
        flag = 1;
        return;
    }
    for(int i = 0; i < 8; i++)
    {
        int xx = x+dx[i];
        int yy = y+dy[i];
        if(xx >= 1 && xx <= p && yy >= 1 && yy <= q && !vis[xx][yy] && !flag)
        {
            vis[xx][yy] = 1;
            dfs(xx, yy, step+1);
            vis[xx][yy] = 0;
        }
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    int cn = 0;
    while(T--)
    {
        scanf("%d %d", &p, &q);
        flag = 0;
        memset(vis, 0, sizeof vis);
        vis[1][1] = 1;
        dfs(1, 1, 1);
        printf("Scenario #%d:\n", ++cn);
        if(!flag)printf("impossible\n");
        else {
            for(int i = 1; i <= p*q; i++){
               printf("%c%d", path[i][1]+'A'-1, path[i][0]);
            }
            printf("\n");
        }
        if(T != 0)printf("\n");
        }
    return 0;
}