【Luogu】【关卡2-7】深度优先搜索（2017年10月）【AK】【题解没写完】

任务说明：搜索可以穷举各种情况。很多题目都可以用搜索完成。就算不能，搜索也是骗分神器。

P1219 八皇后

直接dfs。对角线怎么判断：同一条对角线的横纵坐标的和或者差相同。

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cmath>
 6 
 7 using namespace std;
 8 
 9 static int total = 0;
10 vector<vector<int>> ans;
11 
12 void print(int t, vector<vector<bool>>& chess) {
13     printf("the %dth answer
", t);
14     for(int i = 0; i < chess.size(); ++i) {
15         for(int j = 0; j < chess[i].size(); ++j) {
16             //printf("%d", chess[i][j]);
17             cout << chess[i][j];
18         }
19         printf("
");
20     }
21 }
22 
23 void print(int t, vector<int>& current_ans) {
24     //printf("the %dth answer
", t);
25     printf("%d", current_ans[0]);
26     for(int i = 1; i < current_ans.size(); ++i) {
27             printf(" %d", current_ans[i]);
28     }
29     printf("
");
30 }
31 
32 
33 void queuens(vector<vector<bool>>& chess, int i, const int N,
34              vector<int>& cols, vector<int>& diagnals, vector<int>& anti_diagnals,
35              vector<int>& current_answer) {
36     if (i == N) {
37         total++;
38         if (total <= 3) {
39             print(total, current_answer);
40         }
41         return;
42     }
43     for(int col = 0; col < N; ++col) {
44         if(cols[col] == 0 && anti_diagnals[i-col+N] == 0 && diagnals[i+col] == 0) {
45             cols[col] = 1; anti_diagnals[i-col+N] = 1 ; diagnals[i+col] = 1;
46             current_answer[i] = col+1;
47             queuens(chess, i+1, N, cols, diagnals, anti_diagnals, current_answer);
48             cols[col] = 0; anti_diagnals[i-col+N] = 0 ; diagnals[i+col] = 0;
49             current_answer[i] = 0;
50         }
51     }
52 }
53 
54 
55 int main() {
56     int N;
57     cin >> N;
58     vector<vector<bool>> chess(N, vector<bool>(N, false));
59     vector<int> diagnals(2*N-1, 0);
60     vector<int> anti_diagnals(2*N-1, 0);
61     vector<int> cols(N, 0);
62     vector<int> current_answer(N, 0);
63     queuens(chess, 0, N, cols, diagnals, anti_diagnals, current_answer);
64     printf("%d
", total);
65     return 0;
66 }

View Code

P1019 单词接龙

做的时候没写题解，结果现在忘记了。。。orz

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <utility>
 5 #include <string>
 6 #include <cstring>
 7 #include <vector>
 8 using namespace std;
 9 
10 typedef pair<string, int> P;
11 static int maxans = 0;
12 
13 
14 void print (vector<string>& vecStr) {
15     printf("vector dragon
");
16     for(auto ele : vecStr) {
17         printf("%s ", ele.c_str());
18     }
19     printf("
");
20 }
21 
22 void dfs(int level, vector<P>& vecWord, int& ans, vector<string>& dragon)
23 {
24     string lastWord = dragon[level-1];
25     //printf("info for debug: level[%d] 
", level);
26     //printf("lastWord[%s]", lastWord.c_str());
27     //print(dragon);
28 
29     for (int i = 0; i < vecWord.size(); ++i) {
30         if(vecWord[i].second < 2) {
31             string curWord = vecWord[i].first;
32             int startIdx;
33             if (level == 1) { startIdx = 0; }
34             else {startIdx = 1;}
35             for (int j = lastWord.size() - 1; j >= startIdx; --j) {
36                 string lssubstr = lastWord.substr(j);
37                 if (curWord.find(lssubstr) != 0 || curWord == lssubstr) { continue; }
38                 vecWord[i].second++;
39                 dragon[level] = curWord;
40                 ans += curWord.size() - lssubstr.size();
41                 if (ans > maxans) {maxans = ans;}
42                 dfs(level+1, vecWord, ans, dragon);
43                 dragon[level] = "";
44                 vecWord[i].second--;
45                 ans -= curWord.size() - lssubstr.size();
46             }
47         }
48     }
49 }
50 
51 int main() {
52     int n;
53     cin >> n;
54     vector<P> vecWord(n);
55     for(int i = 0; i < n; ++i) {
56         string str;
57         cin >> str;
58         P p;
59         p.first = str;
60         p.second = 0;
61         vecWord[i] = p;
62     }
63     vector<string> vecDragon(2*n+1);
64     string strDragon;
65     cin >> strDragon;
66 
67     vecDragon[0] = strDragon;
68     int ans = 1;
69     dfs(1, vecWord, ans, vecDragon);
70     cout << maxans << endl;
71     return 0;
72 }

View Code

P1101 单词方阵

就是在一个字母方阵中画出 “yizhong” 这个单词，八种方向都ok，但是一旦选定了方向，就不能换了。

如图：

解法：我的解法就是用一个相同的布尔方阵去决定这个字母是否显示，dfs决定use方阵的01。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <utility>
 5 #include <string>
 6 #include <cstring>
 7 #include <vector>
 8 using namespace std;
 9 
10 string pattern = "yizhong";
11 
12 void print (vector<vector<char>>& chess, vector<vector<bool>>& use) {
13     for(int i = 0; i < chess.size(); ++i) {
14         for (int j = 0; j < chess.size(); ++j) {
15             if (use[i][j]) { printf("%c", chess[i][j]);}
16             else { printf("*"); }
17         }
18         printf("
");
19     }
20 }
21 
22 bool dfs(vector<vector<char>>& chess, vector<vector<bool>>& use, int level, const int addx, const int addy, int x, int y) {
23     if (level == 7) {
24         return true;
25     }
26     if (x+addx >= 0 && x+addx < chess.size() && y+addy >= 0 && y+addy < chess.size()) {
27         if (pattern[level] == chess[x+addx][y+addy]) {
28             bool ans = dfs(chess, use, level+1, addx, addy, x+addx, y+addy);
29             if (ans) {
30                 use[x+addx][y+addy] = ans;
31             }
32             return ans;
33         }
34         else {
35             return false;
36         }
37     } else {
38         return false;
39     }
40 }
41 
42 void findword(vector<vector<char>>& chess, vector<vector<bool>>& use, int x, int y) {
43     for(int addx = -1; addx <= 1; ++addx) {
44         for(int addy = -1; addy <= 1; ++addy) {
45             if (addx == 0 && addy == 0) { continue; }
46             if (x+addx >= 0 && x+addx < chess.size() && y+addy >= 0 && y+addy < chess.size()) {
47                 bool ans = dfs(chess, use, 1, addx, addy, x, y);
48                 if (ans) {
49                     use[x][y] = ans;
50                 }
51             }
52         }
53     }
54 
55 }
56 
57 
58 int main() {
59     int n;
60     cin >> n;
61     vector<vector<char>> chess(n, vector<char>(n));
62 
63     int x = -1, y = -1;
64     for(int i = 0; i < n; ++i) {
65         for (int j = 0; j < n; ++j) {
66             cin >> chess[i][j];
67             if (chess[i][j] == 'y' && x == -1 && y == -1) {
68                 x = i, y = j;
69             }
70         }
71     }
72     vector<vector<bool>> use(n, vector<bool>(n, false));
73     if (x == -1 && y == -1) {
74         print(chess, use);
75         return 0;
76     }
77 
78     for(int i = 0; i < chess.size(); ++i) {
79         for(int j = 0; j < chess[0].size(); ++j) {
80             if (chess[i][j] == 'y') {
81                 findword(chess, use, i, j);
82             }
83         }
84     }
85     print(chess, use);
86 
87 
88     return 0;
89 }

View Code

P1605 迷宫

给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

解答：我是直接dfs，爆搜出来的...题面只给了坐标，需要用坐标复现出棋盘的样子，然后爆搜就好

第一次提交70分，原因在于迷宫的起点也不能重复通过。

//initialize chess,
//state = 0 can go
//state = -1 obstacle
//state = 1 visited

 1 //1605
 2 //第一次提交70分， 问题在于迷宫起点也不能重复通过
 3 
 4 #include <iostream>
 5 #include <vector>
 6 #include <cstdio>
 7 #include <cstdlib>
 8 #include <cmath>
 9 
10 using namespace std;
11 
12 static int ans = 0;
13 int n, m, t;
14 int sx, sy, dx, dy;
15 
16 int addx[4] = {0, -1, 0, 1};
17 int addy[4] = {-1, 0, 1, 0};
18 
19 void print(const vector<vector<int>>& chess) {
20     printf("======begin debug=======
");
21     for(int i = 0; i < chess.size(); ++i) {
22         for(int j = 0; j < chess[0].size(); ++j) {
23             printf("%d ", chess[i][j]);
24         }
25         printf("
");
26     }
27     printf("=======end==============
");
28 }
29 
30 
31 void dfs(vector<vector<int>>& chess, int x, int y) {
32     if (x == dx && y == dy) {
33         ++ans;
34         return;
35     }
36     for(int i = 0; i < 4; ++i) {
37         int newx = x + addx[i], newy = y + addy[i];
38         if(newx > 0 && newx <= n && newy > 0 && newy <= m && chess[newx][newy] != -1 && chess[newx][newy] != 1) {
39             chess[newx][newy] = 1;
40             dfs(chess, newx, newy);
41             chess[newx][newy] = 0;
42         }
43     }
44 }
45 
46 
47 int main() {
48 
49     cin >> n >> m >> t;
50     cin >> sx >> sy >> dx >> dy;
51     //initialize chess,
52     //state = 0 can go
53     //state = -1 obstacle
54     //state = 1 visited
55 
56     vector<vector<int>> chess(n+1, vector<int>(m+1, 0));
57     for(int i = 0; i < m+1; ++i) {
58         chess[0][i] = -1;
59     }
60     for (int i = 0; i < n+1; ++i) {
61         chess[i][0] = -1;
62     }
63     while(t--) {
64         int x, y;
65         cin >> x >> y;
66         chess[x][y] = -1;
67     }
68     //print(chess);
69     chess[sx][sy] = 1; //start point can not repeat pass
70     dfs(chess, sx, sy);
71 
72     cout << ans << endl;
73     return 0;
74 }

View Code