HDU1241 Oil Deposits(DFS模板题)，HZAU 1097 Yuchang and Zixiang ‘s maze(BFS模板题)，P1683 入门(bfs搜索没有终点)，P1162 填涂颜色(BFS联通块)，Poj-1321(DFS逐层搜索)，HDU-2553(N皇后）

HDU1241 Oil Deposits(DFS模板题)

题目：HDU1241

大意：和迷宫的输入差不多，‘*’是墙，‘@’是油田，以一个油田为中心，如果它的东南西北一个各个角落，一共八个方向也有油田的话，这些油田就算作一个油田。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstring>
#include<cstdio>
char a[102][102];
int row,col;
int dir[8][2]= //八个方向
{
    {1, 0},
    {0, 1},
    {-1, 0},
    {0, -1},
    {1, 1},
    {1, -1},
    {-1, 1},
    {-1, -1}
};
using namespace std;
void dfs(int i,int j)
{
    a[i][j]='*'; //扫描过后就将@变成*，防止下次重复搜索
    for (int k=0;k<8;k++)
    {
        int x=i+dir[k][0]; //开始搜索
        int y=j+dir[k][1];
        if (x>=1&&x<=row&&y>=1&&y<=col&&a[x][y]=='@')
            dfs(x,y);
    }
    return ;
}
int main()
{
    while ((cin>>row>>col)&&(row!=0||col!=0))
    {
        int c=0;
        getchar();
        for (int i=1;i<=row;i++)
            for (int j=1;j<=col;j++)
            cin>>a[i][j];
        for (int i=1;i<=row;i++)
            for (int j=1;j<=col;j++)
            if (a[i][j]=='@')
            {
                dfs(i,j);
                c++;
            }
        cout << c << endl;
    }
    return 0;
}

HZAU 1097 Yuchang and Zixiang ‘s maze(BFS模板题)

题目：HZAU 1097 Yuchang and Zixiang ‘s maze

大意：给出起点和终点，还有一些不能走的地方，求走到终点的最短步数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int maxLen = 1100;
int vis[maxLen][maxLen]; //判断有没有走过了
char Map[maxLen][maxLen];	
int step[maxLen][maxLen];	//步数计数

int dir[4][2] = //四个方向
{
    {-1, 0},
    {1, 0},
    {0, 1},
    {0, -1}
};

struct point 
{
    int x, y;	//位置
}in, out, beg;	//入队的值，出队的值，开始的值

int n, m, t, X, Y, a, b, c, d; 

int check(int x, int y) //检查边界或者是否终点
{
    if(!vis[x][y] && x >= 1 && y >= 1 && x <= n && y <= m && Map[x][y] != '#')
        return 1;
    return 0;
}

int bfs()
{
    memset(vis, 0, sizeof(vis)); //刚开始哪个都没有访问
    memset(step, 0, sizeof(step));	//刚开始步数为0
    vis[beg.x][beg.y] = 1; //第一个队列的元素，然后标记为已经访问过了
    step[beg.x][beg.y] = 0; //还没有开始走，步数为0
    queue<point>q;
    q.push(beg); //将第一个元素入队
    while(!q.empty())
    {
        out = q.front(); //将第一个元素出队
        q.pop();
        for(int i = 0; i < 4; i++) //四个方向开始走
        {
            in.x = out.x + dir[i][0];
            in.y = out.y + dir[i][1];
            if(check(in.x, in.y))
            {
                if(Map[in.x][in.y] == 'E') //终点，直接输出那个元素的步数，因为走到E，step数组还没有+1，所以要+1
                    return step[out.x][out.y] + 1;
                q.push(in); //否则入队
                vis[in.x][in.y] = 1; //访问过了
                step[in.x][in.y] = step[out.x][out.y] + 1; //步数累加
            }
        }
    }
    return -1; //没有找到，返回-1
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n >> m >> t)
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                Map[i][j] = '.';
        for(int i = 0; i < t; i++)
        {
            cin >> X >> Y;
            Map[X][Y] = '#';
        }
        cin >> a >> b >> c >> d; //从ab走到cd
        if(a == c && b == d) cout << "0" << endl; //同一个位置不用走
        else
        {
            beg.x = a;
            beg.y = b;
            int ans = bfs();
        	cout << ans << endl;
        }
    }
    return 0;
}

P1683 入门(bfs搜索没有终点)

题目：p1683

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int len = 300;

char Map[len][len];
int vis[len][len] = {0};
int ans = 0;
int w, h;
struct point
{
    int x, y;
}in, out, beg;
queue<point> q;
int dir[4][2] =
{
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};

int check(int x, int y)
{
    if(!vis[x][y] && x >= 1 && y >= 1 && x <= h && y <= w
            && Map[x][y] != '#')
        return 1;
    return 0;
}

void bfs(int x, int y)
{
    vis[beg.x][beg.y] = 1;
    q.push(beg);
    while(!q.empty())
    {
        out = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            in.x = out.x + dir[i][0];
            in.y = out.y + dir[i][1];
        //    cout << in.x << " " << in.y << endl;
            if(check(in.x, in.y)) //这里改了下就行了，如果符合条件就会自己走，不符合条件的话就结束函数
            {
                q.push(in);
                vis[in.x][in.y] = 1;
                ans++;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> w >> h;
    for(int i = 1; i <= h; i++)
        for(int j = 1; j <= w; j++)
        {
            cin >> Map[i][j];
            if(Map[i][j] == '@')
            {
                beg.x = i;
                beg.y = j;
            }
        }
    bfs(beg.x, beg.y);
    cout << ans + 1;
    return 0;
}

P1162 填涂颜色(BFS联通块)

p1162

所有不在圈内的0组成的块，必定会触碰边界。

所以从边界上的0开始进行广搜，把搜过的进行标记，那么没搜过的也不是1的就是要找的2了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int maxLen = 1100;
int vis[maxLen][maxLen]; //判断有没有走过了
int Map[maxLen][maxLen];

int dir[4][2] = //四个方向
        {
                {-1, 0},
                {1, 0},
                {0, 1},
                {0, -1}
        };

struct point
{
    int x, y;	//位置
}in, out, beg;	//入队的值，出队的值，开始的值

int n;

int check(int x, int y) //检查边界或者是否终点
{
    if(!vis[x][y] && x >= 1 && y >= 1 && x <= n && y <= n && Map[x][y] != 1)
        return 1;
    return 0;
}

void bfs()
{
    memset(vis, 0, sizeof(vis)); //刚开始哪个都没有访问
    queue<point>q;
    //下面四个for循环表示搜索最外一层，如果某个位置为0，那么就搜索，没有的话就不用了
    for(int i = 1; i <= n; i++) 
    {
        if(Map[1][i] == 0)
        {
            beg.x = 1;
            beg.y = i;
            vis[beg.x][beg.y] = 1;
            q.push(beg);
        }
    }

    for(int i = 1; i <= n; i++)
    {
        if(Map[i][1] == 0)
        {
            beg.x = i;
            beg.y = 1;
            vis[beg.x][beg.y] = 1;
            q.push(beg);
        }
    }

    for(int i = 1; i < n; i++)
    {
        if(Map[i][n] == 0)
        {
            beg.x = i;
            beg.y = n;
            vis[beg.x][beg.y] = 1;
            q.push(beg);
        }
    }

    for(int i = 1; i < n; i++)
    {
        if(Map[n][i] == 0)
        {
            beg.x = n;
            beg.y = i;
            vis[beg.x][beg.y] = 1;
            q.push(beg);
        }
    }

    while(!q.empty())
    {
        out = q.front(); //将第一个元素出队
        q.pop();
        for(int i = 0; i < 4; i++) //四个方向开始走
        {
            in.x = out.x + dir[i][0];
            in.y = out.y + dir[i][1];
            if(check(in.x, in.y))
            {
                q.push(in); //入队
                vis[in.x][in.y] = 1; //访问过了
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> Map[i][j];
    bfs();
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(!vis[i][j] && Map[i][j] == 0) //没被访问过，同时为0，就输出2
                cout << 2 << " ";
            else
                cout << Map[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Poj-1321(DFS逐层搜索)

POJ - 1321

棋子放在’#’, ‘.’不能放棋子，求满足条件的摆放方案次数，和八皇后问题相似，这次采用的办法是逐层DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//Code 1
/*
Memory: 672K		Time: 47MS
Language: G++		Result: Accepted
*/
#include <iostream>
#include <cstring>
using namespace std;

const int maxLen = 10;
char chess[maxLen][maxLen];
bool vis[10] = {false}; //用来记录某一列有没有被标记
int row, k, ans = 0;

void dfs(int r, int cnt) //r代表行数，cnt代表放的是已经放的棋子的个数
{
    /*
    	这两个if能不能调换？
    	不能，如果调换了会导致不能ans++，因为已经ruturn，但是dfs是满足条件后才dfs(r + 1, cnt + 1);
    	这时候已经满足条件了，得ans++，但是r+1可能会导致r>row
    */
    if(cnt == k)
    {
        ans++;
        return;
    }
    if(r > row)
        return;

        for(int i = 1; i <= row; i++) //搜索这一行的全部列
        {
            if(chess[r][i] == '#' && !vis[i]) //满足条件
            {
                vis[i] = true; //标记这一列已经走过了
                dfs(r + 1, cnt + 1); //接着走下一行，对应的棋子数要加1
                vis[i] = false; //dfs(r + 1, cnt + 1);结束后i继续++，走别的列，那么刚刚那一列就要标记为没有走过
            }
        }
        dfs(r + 1, cnt);
    /*
	4 2
	#...
	##..
	...#
	..#.
	处理这种情况，当k<row时，得走完所有的行
    */
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> row >> k && row != -1 && k != -1)
    {
        memset(vis, false, sizeof(vis));
        for(int i = 1; i <= row; i++)
            for(int j = 1; j <= row; j++)
                cin >> chess[i][j];
        dfs(1, 0); //代表从第一行开始逐层dfs，放的棋子的数目为0
        cout << ans << endl;
        ans = 0;
    }
    return 0;
}

//code2(思路一样)
/*
Memory: 672K		Time: 47MS
Language: G++		Result: Accepted
*/
#include <iostream>
#include <cstring>
using namespace std;

const int maxLen = 10;
char chess[maxLen][maxLen];
bool vis[10] = {false};
int row, k, ans = 0;

void dfs(int r, int cnt)
{
    if(cnt == k)
    {
        ans++;
        return;
    }
    /*
        不需要
    if(r > row)
        return;
    */
    for(int j = r + 1; j <= row; j++) //这里代表搜索下一行，所有dfs起始是dfs(0,0)，这样的话就不能搜索完所有的行
        for(int i = 1; i <= row; i++)
        {
            if(chess[j][i] == '#' && !vis[i])
            {
                vis[i] = true;
                dfs(j, cnt + 1);
                vis[i] = false;
            }
        }
}

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> row >> k && row != -1 && k != -1)
    {
        memset(vis, false, sizeof(vis));
        for(int i = 1; i <= row; i++)
            for(int j = 1; j <= row; j++)
                cin >> chess[i][j];
        dfs(0, 0);
        cout << ans << endl;
        ans = 0;
    }
    return 0;
}

test:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2 1
#.
.#
4 4
...#
..#.
.#..
#...
4 2
#...
##..
...#
..#.
3 2
#.#
##.
#.# 
2 2
#.
.#
2 1
#.
#. 
8 8
########
########
########
########
########
########
########
######## 
-1 -1

2
1
8
8
1
2
40320

HDU-2553(N皇后)

HDU - 2553

这道题是上道题(poj-1321)的加强版，意思是说多了个限制条件，对角线限制，按照上道题来，我们可以逐层搜索，然后标记列和对角线就行了，但是怎么标记对角线呢？

参考HDU 2553 N皇后问题（详细题解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
Status:Accepted							Time:46ms
Memory:1808kB							Length:753
Lang:C++
*/
#include <iostream>
#include <cstring>
using namespace std;
int n, ans = 0;
int vis[5][100];
int ANS[20];
void dfs(int r, int cnt)
{
    if(cnt == n)
    {
        ans++;
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(!vis[0][i] && !vis[1][r + i] && !vis[2][r - i + n])
        {
            vis[0][i] = vis[1][r + i] = vis[2][r - i + n] = 1;
            dfs(r + 1, cnt + 1);
            vis[0][i] = vis[1][r + i] = vis[2][r - i + n] = 0;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    for(n = 1; n <= 10; n++) //这道题得打表，不然超时
    {
        memset(vis, 0, sizeof(vis));
        ans = 0;
        dfs(1, 0);
        ANS[n] = ans;
    }
    while(cin >> n && n != 0)
    {
        cout << ANS[n] << endl;
    }
    return 0;
}