kuangbin专题和洛谷专题的刷题记录,以及简单搜索总结
知识点
白书例题(DFS + 简单剪枝)
给定整数a1 、a2 …、an ,判断是否可以从中选出若干数,使他们的和恰好为k。
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 #include <iostream> #include <algorithm> using namespace std;const int MAX_N = 20 ;int n;int a[MAX_N];int k;bool dfs (int i, int sum) { if (sum > k) return false ; if (i == n) return sum == k; if (dfs (i+1 , sum)) return true ; if (dfs (i+1 , sum+a[i])) return true ; return false ; } int main () { cin >> n; for (int i=0 ; i<n; ++i) cin >> a[i]; cin >> k; if (dfs (0 , 0 )) printf ("yes\n" ); else printf ("no\n" ); return 0 ; }
POJ1321(DFS,八皇后变式)
类似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 46 47 48 49 50 51 #include <cstdio> #include <cstring> const int MAX_N = 8 ;char map[MAX_N+1 ][MAX_N+1 ];int n, k, ans = 0 ;bool check[MAX_N+1 ];void dfs (int x, int now) { if (x == n && now != k) return ; if (now == k) { ans++; return ; } else { for (int i = 0 ; i < n; ++i) { if (map[x][i] == '#' && !check[i]) { check[i] = 1 ; dfs (x+1 , now+1 ); check[i] = 0 ; } } dfs (x+1 , now); } } int main () { while (true ) { scanf ("%d%d" , &n, &k); if (n == -1 && k == -1 ) break ; for (int i = 0 ; i < n; ++i) { scanf ("%s" , map[i]); } ans = 0 ; memset (check, 0 , sizeof (check)); dfs (0 , 0 ); printf ("%d\n" , ans); } return 0 ; }
POJ2251(三维BFS)
简单扩展下二维BFS,用结构体表示坐标即可
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 #include <cstdio> #include <queue> using namespace std;struct Node { int l; int r; int c; }; const int MAX_LRC = 30 + 1 ;const int INF = 1e9 ;char maze[MAX_LRC][MAX_LRC][MAX_LRC];int t[MAX_LRC][MAX_LRC][MAX_LRC];int L, R, C;int sl, sr, sc;int el, er, ec;int dl[] = {1 , -1 , 0 , 0 , 0 , 0 };int dr[] = {0 , 0 , 1 , -1 , 0 , 0 };int dc[] = {0 , 0 , 0 , 0 , 1 , -1 };void bfs () { queue<Node> que; Node q; q.l = sl; q.r = sr; q.c = sc; que.push (q); while (que.size ()) { Node qu = que.front (); que.pop (); for (int i = 0 ; i < 6 ; ++i) { Node qe; qe.l = qu.l + dl[i]; qe.r = qu.r + dr[i]; qe.c = qu.c + dc[i]; if (qe.l >= 0 && qe.l < L && qe.r >= 0 && qe.r < R && qe.c >= 0 && qe.c < C && maze[qe.l][qe.r][qe.c] != '#' && t[qe.l][qe.r][qe.c] == INF) { que.push (qe); t[qe.l][qe.r][qe.c] = t[qu.l][qu.r][qu.c] + 1 ; } } } } int main () { while (true ) { scanf ("%d%d%d" , &L, &R, &C); if (L == 0 ) break ; for (int i = 0 ; i < L; ++i) { for (int j = 0 ; j < R; ++j) { scanf ("%s" , maze[i][j]); for (int k = 0 ; k < C; ++k) { t[i][j][k] = INF; if (maze[i][j][k] == 'S' ) { sl = i; sr = j; sc = k; } else if (maze[i][j][k] == 'E' ) { el = i; er = j; ec = k; } } } } t[sl][sr][sc] = 0 ; bfs (); if (t[el][er][ec] == INF) printf ("Trapped!\n" ); else printf ("Escaped in %d minute(s).\n" , t[el][er][ec]); } return 0 ; }
POJ3278(非图类BFS)
其实这题就是步长不同的BFS
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 #include <cstdio> #include <queue> using namespace std;const int MAX_N = 1e5 + 1 ;int n, k;int ans[MAX_N];void bfs () { queue<int > que; que.push (n); while (que.size ()) { int p = que.front (); que.pop (); if (p == k) break ; for (int i = 0 ; i < 3 ; ++i) { int t; if (i == 0 ) t = p - 1 ; else if (i == 1 ) t = p + 1 ; else t = p * 2 ; if (t >= 0 && t <= MAX_N && !ans[t]) { que.push (t); ans[t] = ans[p] + 1 ; } } } } int main () { scanf ("%d%d" , &n, &k); bfs (); printf ("%d\n" , ans[k]); return 0 ; }
POJ3279(集合的整数表示 + 枚举)
感觉不像搜索……
需要枚举集合,用到集合的整数表示
第一行情况固定了,后面每一行的翻转情况也就确定了
我的方法比较傻,所以再贴一个白书上的题解
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 119 120 121 122 123 124 125 #include <cstdio> #include <cstring> const int MAX_N = 15 + 1 ;int rec[MAX_N][MAX_N];int rect[MAX_N][MAX_N];int t[MAX_N][MAX_N];int ans[MAX_N][MAX_N];int dx[] = {1 , 0 , 0 , -1 , 0 };int dy[] = {0 , 1 , 0 , 0 , -1 };int N, M;bool check (int x, int y) { return (0 <= x && x < M && 0 <= y && y < N); } void flip (int x, int y) { for (int i = 0 ; i < 5 ; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (check (nx, ny)) { rect[nx][ny] = !rect[nx][ny]; } } } int solve () { for (int i = 1 ; i < M; ++i) { for (int j = 0 ; j < N; ++j) { if (rect[i - 1 ][j]) { flip (i, j); t[i][j] = 1 ; } } } for (int j = 0 ; j < N; ++j) { if (rect[M - 1 ][j]) return -1 ; } int res = 0 ; for (int i = 0 ; i < M; ++i) { for (int j = 0 ; j < N; ++j) { if (t[i][j]) res += 1 ; } } return res; } int main () { int res = -1 ; scanf ("%d%d" , &M, &N); for (int i = 0 ; i < M; ++i) { for (int j = 0 ; j < N; ++j) { scanf ("%d" , &rec[i][j]); } } for (int i = 0 ; i < 1 << N; ++i) { memset (t, 0 , sizeof (t)); memcpy (rect, rec, sizeof (rec)); for (int j = 0 ; j < N; ++j) { t[0 ][N - 1 - j] = i >> j & 1 ; } for (int k = 0 ; k < N; ++k) { if (t[0 ][k]) flip (0 , k); } int num = solve (); if (num >= 0 && (res < 0 || res > num)) { res = num; memcpy (ans, t, sizeof (t)); } } if (res == -1 ) printf ("IMPOSSIBLE\n" ); else { for (int j = 0 ; j < M; ++j) { for (int k = 0 ; k < N; ++k) { printf ("%d " , ans[j][k]); } printf ("\n" ); } } return 0 ; }
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 #include <cstdio> #include <cstring> const int MAX_N = 15 + 1 ;const int MAX_M = 15 + 1 ;const int dx[5 ] = {-1 , 0 , 0 , 0 , 1 };const int dy[5 ] = {0 , -1 , 0 , 1 , 0 };int M, N;int tile[MAX_M][MAX_N];int opt[MAX_M][MAX_N];int flip[MAX_M][MAX_N];int get (int x, int y) { int c = tile[x][y]; for (int d = 0 ; d < 5 ; ++d) { int x2 = x + dx[d]; int y2 = y + dy[d]; if (0 <= x2 && x2 < M && 0 <= y2 && y2 < N) { c += flip[x2][y2]; } } return c % 2 ; } int calc () { for (int i = 1 ; i < M; ++i) { for (int j = 0 ; j < N; ++j) { if (get (i - 1 , j) != 0 ) { flip[i][j] = 1 ; } } } for (int j = 0 ; j < N; ++j) { if (get (M - 1 , j) != 0 ) return -1 ; } int res = 0 ; for (int i = 0 ; i < M; ++i) { for (int j = 0 ; j < N; ++j) { res += flip[i][j]; } } return res; } void solve () { int res = -1 ; for (int i = 0 ; i < 1 << N; ++i) { memset (flip, 0 , sizeof (flip)); for (int j = 0 ; j < N; ++j) { flip[0 ][N - j - 1 ] = i >> j & 1 ; } int num = calc (); if (num >= 0 && (res < 0 || res > num)) { res = num; memcpy (opt, flip, sizeof (flip)); } } if (res < 0 ) { printf ("IMPOSSIBLE\n" ); } else { for (int i = 0 ; i < M; ++i) { for (int j = 0 ; j < N; ++j) { printf ("%d%c" , opt[i][j], j + 1 == N ? '\n' : ' ' ); } } } } int main () { scanf ("%d%d" , &M, &N); for (int i = 0 ; i < M; ++i) { for (int j = 0 ; j < N; ++j) { scanf ("%d" , &tile[i][j]); } } solve (); return 0 ; }
POJ1426(BFS + 思考)
再字符串后分别加0和1,然后判断余数,若余数没有出现过,则是一个新状态,加入队列
可以用除法列竖式来理解算法思路
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 #include <cstdio> #include <iostream> #include <string> #include <queue> #include <cstring> using namespace std;int n;int book[300 ];struct node { int y; string ans; node (int y, string ans) : y (y), ans (ans){} }; void solve () { queue<node> que; que.push (node (1 , "1" )); int yy; while (que.size ()) { node t = que.front (); que.pop (); if (!t.y) { cout << t.ans << '\n' ; return ; } yy = (t.y * 10 + 1 ) % n; if (!book[yy]) { book[yy] = 1 ; que.push (node (yy, t.ans + "1" )); } yy = (t.y * 10 ) % n; if (!book[yy]) { book[yy] = 1 ; que.push (node (yy, t.ans + "0" )); } } } int main () { while (true ) { scanf ("%d" , &n); if (!n) break ; memset (book, 0 , sizeof (book)); solve (); } return 0 ; }
POJ3126(素数筛 + 非图类BFS)
枚举改变一个数字后的所有状态,判断是否是素数,是素数则放入队列
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 #include <cstdio> #include <queue> #include <algorithm> using namespace std;const int MAX_N = 10000 ;bool prime[MAX_N];int d[MAX_N];void init () { for (int i = 1 ; i <= 9999 ; ++i) { prime[i] = true ; } prime[1 ] = false ; } void prim () { init (); for (int i = 2 ; i <= 9999 ; ++i) { if (prime[i]) { for (int j = 2 ; j * i <= 9999 ; ++j) { prime[j * i] = false ; } } } } int n;int a, b;int solve (int a, int b) { if (a == b) return 0 ; queue<int > que; que.push (a); d[a] = 0 ; while (que.size ()) { int t = que.front (); que.pop (); int temp = t / 1000 ; for (int i = 1 ; i < 10 ; ++i) { if (i == temp) continue ; int t1 = i * 1000 + t - temp * 1000 ; if (prime[t1] && d[t1] == -1 ) { d[t1] = d[t] + 1 ; que.push (t1); } } temp = t % 1000 / 100 ; for (int i = 0 ; i < 10 ; ++i) { if (i == temp) continue ; int t1 = i * 100 + t - temp * 100 ; if (prime[t1] && d[t1] == -1 ) { d[t1] = d[t] + 1 ; que.push (t1); } } temp = t % 100 / 10 ; for (int i = 0 ; i < 10 ; ++i) { if (i == temp) continue ; int t1 = i * 10 + t - temp * 10 ; if (prime[t1] && d[t1] == -1 ) { d[t1] = d[t] + 1 ; que.push (t1); } } temp = t % 10 ; for (int i = 0 ; i < 10 ; ++i) { if (i == temp ) continue ; int t1 = t - temp + i; if (prime[t1] && d[t1] == -1 ) { d[t1] = d[t] + 1 ; que.push (t1); } } } return d[b]; } int main () { prim (); scanf ("%d" , &n); for (int i = 0 ; i < n; ++i) { scanf ("%d%d" , &a, &b); fill (d, d + MAX_N, -1 ); int ans = solve (a, b); if (ans == -1 ) printf ("Impossible\n" ); else printf ("%d\n" , ans); } return 0 ; }
POJ3087(打表 + 模拟?)
我已经想到一个绝妙的证明,可惜这里空间太小写不下(皮)
是道模拟题吧,不知道为什么归在搜索。编写很简单,但是证明了一个多小时还证不出来,题解也没有相关证明。
设a1 ,a2 ,…a2n
则新串b1 ,b2 ,…b2n
有bi =a (i & 1 ? i = (i + 1) / 2 : i / 2);
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <cstdio> int main () { int n; n = 10 ; int i = 2 ; while (true ) { if (i & 1 ) i = (i + 1 ) / 2 + n; else i = i / 2 ; printf ("%d\n" , i); } return 0 ; }
打表发现总有一个新i会等于旧i,也就是说,总会有bi = … = ai ,
用反证法。设i0 ,i的范围为(0,2n],如果i0 经过2n次变换,ik 始终不等于i0 ,那么必定有个i出现了两次,而这个i一定由i0 变化而来,所以i0 在变化中出现了循环,也即在2n次变换中,一定存在bi = … = ai 。
但是思路有点问题,bi = … = ai 所用的次数各不相同,无法证明所有的b和a相等……
看看学了离散和具体数学后有没有办法证明吧。
AC代码
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 #include <iostream> #include <string> using namespace std;string str[1000 ]; int t;int len;string str1, str2, str3; bool find (string strn, int sum) { for (int i = 0 ; i < sum; ++i) { if (str[i] == strn) return true ; } return false ; } int main () { cin >> t; for (int i = 0 ; i < t; ++i) { cin >> len; cin >> str1 >> str2 >> str3; int sum = 0 ; while (true ) { string strt = str3; for (int j = 0 ; j < len; ++j) { strt[j*2 ] = str2[j]; strt[j*2 +1 ] = str1[j]; } str[sum] = strt; if (str[sum] == str3) { cout << i+1 << ' ' << sum+1 << '\n' ; break ; } else if (find (str[sum], sum)) { cout << i+1 << ' ' << -1 << '\n' ; break ; } sum++; for (int j = 0 ; j < len; ++j) { str1[j] = strt[j]; str2[j] = strt[len + j]; } } } return 0 ; }
POJ3414(BFS + 思考)
参考自博客https://blog.csdn.net/qq_41280600/article/details/102491233
新思路,变量结构体中一个值储存路径
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 #include <cstdio> #include <iostream> #include <cstring> #include <string> #include <queue> using namespace std;struct node { int a, b; string opt; int step; node (int a, int b, string opt, int step): a (a), b (b), opt (opt), step (step){} }; int a, b, c;int vis[105 ][105 ];string bfs () { queue<node> que; que.push (node (0 , 0 , "" , 0 )); vis[0 ][0 ] = 1 ; while (que.size ()) { node t = que.front (); que.pop (); if (t.a == c || t.b == c) { cout << t.step <<endl; return t.opt; } if (!vis[a][t.b]) { vis[a][t.b] = 1 ; que.push (node (a, t.b, t.opt + "FILL(1)\n" , t.step + 1 )); } if (!vis[t.a][b]) { vis[t.a][b] = 1 ; que.push (node (t.a, b, t.opt + "FILL(2)\n" , t.step + 1 )); } if (t.a != 0 && !vis[0 ][t.b]) { vis[0 ][t.b] = 1 ; que.push (node (0 , t.b, t.opt + "DROP(1)\n" , t.step + 1 )); } if (t.b != 0 && !vis[t.a][0 ]) { vis[t.a][0 ] = 1 ; que.push (node (t.a, 0 , t.opt + "DROP(2)\n" , t.step + 1 )); } if (t.a != 0 && t.b != b) { if (t.a + t.b <= b) { if (!vis[0 ][t.a + t.b]) { vis[0 ][t.a + t.b] = 1 ; que.push (node (0 , t.a + t.b, t.opt + "POUR(1,2)\n" , t.step + 1 )); } } else { if (!vis[t.a + t.b - b][b]) { vis[t.a + t.b - b][b] = 1 ; que.push (node (t.a + t.b - b, b, t.opt + "POUR(1,2)\n" , t.step + 1 )); } } } if (t.b != 0 && t.a != a) { if (t.a + t.b <= a) { if (!vis[t.a + t.b][0 ]) { vis[t.a + t.b][0 ] = 1 ; que.push (node (t.a + t.b, 0 , t.opt + "POUR(2,1)\n" , t.step + 1 )); } } else { if (!vis[a][t.a + t.b - a]) { vis[a][t.a + t.b - a] = 1 ; que.push (node (a, t.a + t.b - a, t.opt + "POUR(2,1)\n" , t.step + 1 )); } } } } return "impossible" ; } int main () { scanf ("%d%d%d" , &a, &b, &c); cout << bfs (); return 0 ; }
FZU2150(双点BFS) 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 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std;const int MAX_N = 20 ;const int INF = 2e9 + 7 ;int T, n, m;char maze[MAX_N][MAX_N];char book[MAX_N][MAX_N];int ans;int dx[] = {1 , 0 , -1 , 0 };int dy[] = {0 , 1 , 0 , -1 };int d[MAX_N][MAX_N];typedef pair<int , int > pr;queue<pr> que; void my_fill (int x, int y) { book[x][y] = '.' ; for (int i = 0 ; i < 4 ; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (0 <= nx && nx < n && 0 <= ny && ny < m && book[nx][ny] == '#' ) my_fill (nx, ny); } } bool check () { int count = 0 ; for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < m; ++j) { if (book[i][j] == '#' ) { my_fill (i, j); count++; } } } if (count > 2 ) return false ; return true ; } int solve (int x, int y, int a, int b) { int ret = 0 ; queue<pr> p; p.push (pr (x, y)); p.push (pr (a, b)); d[x][y] = d[a][b] = 0 ; while (p.size ()) { pr t = p.front (); p.pop (); for (int i = 0 ; i < 4 ; ++i) { int nx = t.first + dx[i]; int ny = t.second + dy[i]; if (0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] == '#' && d[nx][ny] == -1 ) { ret = d[nx][ny] = d[t.first][t.second] + 1 ; p.push (pr (nx, ny)); } } } for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < m; ++j) { if (maze[i][j] == '#' && d[i][j] == -1 ) { return INF; } } } return ret; } int main () { scanf ("%d" , &T); for (int i = 0 ; i < T; ++i) { que = queue <pr>(); ans = INF; scanf ("%d%d" , &n, &m); for (int i = 0 ; i < n; ++i) { scanf ("%s" , maze[i]); for (int j = 0 ; j < m; ++j) { book[i][j] = maze[i][j]; if (maze[i][j] == '#' ) { que.push (pr (i, j)); } } } if (!check ()) { printf ("Case %d: -1\n" , i + 1 ); continue ; } if (que.size () <= 2 ) { printf ("Case %d: 0\n" , i + 1 ); continue ; } while (que.size ()) { pr t1 = que.front (); que.pop (); int count = que.size (); while (count--) { pr t2 = que.front (); que.pop (); que.push (t2); memset (d, -1 , sizeof (d)); ans = min (ans, solve (t1.first, t1.second, t2.first, t2.second)); } } printf ("Case %d: %d\n" , i + 1 , ans); } return 0 ; }
UVA11624(多点BFS)
F的初始位置有很多,用一个队列来存储F,j可达到的地方也用一个队列表示
然后就是双起点BFS了
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 #include <cstdio> #include <queue> #include <cstring> using namespace std;const int MAX_N = 1000 + 1 ;typedef pair<int , int > pr;int n;int r, c;char maze[MAX_N][MAX_N];int d[MAX_N][MAX_N];int dx[] = {1 , 0 , -1 , 0 };int dy[] = {0 , 1 , 0 , -1 };int jx, jy;int ret = 0 ;queue<pr> F; bool solve () { queue<pr> qj; qj.push (pr (jx, jy)); d[jx][jy] = 0 ; while (qj.size ()) { int count = F.size (); while (count--) { pr t2 = F.front (); F.pop (); for (int i = 0 ; i < 4 ; ++i) { int nx = t2.first + dx[i]; int ny = t2.second + dy[i]; if (0 <= nx && nx < r && 0 <= ny && ny < c && (maze[nx][ny] == '.' || maze[nx][ny] == 'J' )) { maze[nx][ny] = 'F' ; F.push (pr (nx, ny)); } } } count = qj.size (); while (count--) { pr t = qj.front (); qj.pop (); for (int i = 0 ; i < 4 ; ++i) { int nx = t.first + dx[i]; int ny = t.second + dy[i]; if (0 <= nx && nx < r && 0 <= ny && ny < c) { if (d[nx][ny] == -1 && maze[nx][ny] == '.' ) { d[nx][ny] = d[t.first][t.second] + 1 ; qj.push (pr (nx, ny)); } } else { ret = d[t.first][t.second] + 1 ; return true ; } } } } return false ; } int main () { scanf ("%d" , &n); for (int i = 0 ; i < n; ++i) { F = queue <pr>(); memset (d, -1 , sizeof (d)); scanf ("%d%d" , &r, &c); for (int j = 0 ; j < r; ++j) { scanf ("%s" , maze[j]); for (int k = 0 ; k < c; ++k) { if (maze[j][k] == 'F' ) { F.push (pr (j, k)); } if (maze[j][k] == 'J' ) { jx = j; jy = k; } } } if (solve ()) printf ("%d\n" , ret); else printf ("IMPOSSIBLE\n" ); } return 0 ; }
POJ3984(DFS + 路径还原)
路径还原
我选择用一个栈同步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 #include <cstdio> #include <stack> using namespace std;const int MAX_N = 6 ;int maze[MAX_N][MAX_N];int d[MAX_N][MAX_N];int dx[] = {1 , 0 , -1 , 0 };int dy[] = {0 , 1 , 0 , -1 };int mini = 2e9 ;typedef pair<int , int > pr;stack<pr> s1, s2; void dfs (int x, int y) { if (x == 4 && y == 4 ) { if ((int )s1.size () < mini) { s2 = s1; mini = s1.size (); } return ; } else { for (int i = 0 ; i < 4 ; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (0 <= nx && nx < 5 && 0 <= ny && ny < 5 && !maze[nx][ny] && !d[nx][ny]) { s1.push (pr (nx, ny)); d[nx][ny] = 1 ; dfs (nx, ny); d[nx][ny] = 0 ; s1.pop (); } } } } int main () { for (int i = 0 ; i < 5 ; ++i) for (int j = 0 ; j < 5 ; ++j) scanf ("%d" , &maze[i][j]); s1.push (pr (0 , 0 )); d[0 ][0 ] = 1 ; dfs (0 , 0 ); stack<pr> s3; while (!s2.empty ()) { s3.push (s2.top ()); s2.pop (); } while (!s3.empty ()) { printf ("(%d, %d)\n" , s3.top ().first, s3.top ().second); s3.pop (); } return 0 ; }
HDU1241(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 #include <cstdio> const int MAX_N = 100 + 1 ;int n, m;char map[MAX_N][MAX_N];void dfs (int x, int y) { for (int i = -1 ; i <= 1 ; ++i) { for (int j = -1 ; j <= 1 ; ++j) { int nx = x + i; int ny = y + j; if (0 <= nx && nx < n && 0 <= ny && ny < m && map[nx][ny] == '@' ) { map[nx][ny] = '*' ; dfs (nx, ny); } } } } int main () { while (true ) { int ans = 0 ; scanf ("%d%d" , &n, &m); if (!n) break ; for (int i = 0 ; i < n; ++i) { scanf ("%s" , map[i]); } for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < m; ++j) { if (map[i][j] == '@' ) { dfs (i, j); ans++; } } } printf ("%d\n" , ans); } return 0 ; }
HDU1495(BFS + 枚举 + 思考)
枚举倒完水后各个容器内水的体积,然后BFS即可
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 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 #include <cstdio> #include <queue> #include <cstring> using namespace std;struct node { int x; int y; int z; }; int ans[102 ][102 ][102 ];int solve (int S, int N, int M) { if (S & 1 ) return -1 ; memset (ans, -1 , sizeof (ans)); ans[S][0 ][0 ] = 0 ; queue<node> que; node t; t.x = S, t.y = 0 , t.z = 0 ; que.push (t); while (que.size ()) { t = que.front (); que.pop (); int count = 0 ; if (t.x == S / 2 ) count++; if (t.y == S / 2 ) count++; if (t.z == S / 2 ) count++; if (count == 2 ) return ans[t.x][t.y][t.z]; node t1; if (t.x + t.y <= N) { t1.x = 0 ; t1.y = t.x + t.y; t1.z = t.z; } else { t1.x = t.x + t.y - N; t1.y = N; t1.z = t.z; } if (ans[t1.x][t1.y][t1.z] == -1 ) { que.push (t1); ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1 ; } if (t.x + t.z <= M) { t1.x = 0 ; t1.y = t.y; t1.z = t.x + t.z; } else { t1.x = t.x + t.z - M; t1.y = t.y; t1.z = M; } if (ans[t1.x][t1.y][t1.z] == -1 ) { que.push (t1); ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1 ; } if (t.y + t.z <= M) { t1.x = t.x; t1.y = 0 ; t1.z = t.y + t.z; } else { t1.x = t.x; t1.y = t.y + t.z - M; t1.z = M; } if (ans[t1.x][t1.y][t1.z] == -1 ) { que.push (t1); ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1 ; } if (t.y + t.z <= N) { t1.x = t.x; t1.y = t.y + t.z; t1.z = 0 ; } else { t1.x = t.x; t1.y = N; t1.z = t.y + t.z - N; } if (ans[t1.x][t1.y][t1.z] == -1 ) { que.push (t1); ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1 ; } t1.x = t.x + t.y; t1.y = 0 ; t1.z = t.z; if (ans[t1.x][t1.y][t1.z] == -1 ) { que.push (t1); ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1 ; } t1.x = t.x + t.z; t1.y = t.y; t1.z = 0 ; if (ans[t1.x][t1.y][t1.z] == -1 ) { que.push (t1); ans[t1.x][t1.y][t1.z] = ans[t.x][t.y][t.z] + 1 ; } } return -1 ; } int main () { int S, N, M; while (true ) { scanf ("%d%d%d" , &S, &N, &M); if (!S) break ; int ret = solve (S, N, M); if (ret == -1 ) printf ("NO\n" ); else printf ("%d\n" , ret); } return 0 ; }
HDU2612(两点BFS)
可能有的@点无法到达,要排除
两个BFS,把结果相加即可
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 #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std;const int MAX_N = 200 + 10 ;int n, m;char maze[MAX_N][MAX_N];int ansY[MAX_N][MAX_N];int ansM[MAX_N][MAX_N];int YX, YY;int MX, MY;int ret = 1e9 ;int dx[] = {1 , 0 , -1 , 0 };int dy[] = {0 , 1 , 0 , -1 };typedef pair<int , int > pr;void solve (int x, int y, int (& ans)[MAX_N][MAX_N]) { queue<pr> que; que.push (pr (x, y)); while (que.size ()) { pr t = que.front (); que.pop (); for (int i = 0 ; i < 4 ; ++i) { int nx = t.first + dx[i]; int ny = t.second + dy[i]; if (0 <= nx && 0 <= ny && nx < n && ny < m && maze[nx][ny] != '#' && maze[nx][ny] != 'Y' &&maze[nx][ny] != 'M' && ans[nx][ny] == -1 ) { ans[nx][ny] = ans[t.first][t.second] + 1 ; que.push (pr (nx, ny)); } } } } int main () { while (scanf ("%d%d" , &n, &m) != EOF) { for (int i = 0 ; i < n; ++i) { scanf ("%s" , maze[i]); for (int j = 0 ; j < m; ++j) { if (maze[i][j] == 'Y' ) { YX = i; YY = j; } if (maze[i][j] == 'M' ) { MX = i; MY = j; } } } memset (ansY, -1 , sizeof (ansY)); ansY[YX][YY] = 0 ; solve (YX, YY, ansY); memset (ansM, -1 , sizeof (ansM)); ansM[MX][MY] = 0 ; solve (MX, MY, ansM); ret = 1e9 ; for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < m; ++j) { if (maze[i][j] == '@' && ansY[i][j] != -1 && ansM[i][j] != -1 ) ret = min (ret, ansY[i][j] + ansM[i][j]); } } printf ("%d\n" , ret * 11 ); } return 0 ; }
洛谷P1219(DFS,经典八皇后问题)
经典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 #include <cstdio> int n, sum;int ans[14 ];bool check[3 ][30 ];void solve (int line) { if (line > n) { sum++; if (sum > 3 ) return ; else { for (int i = 1 ; i <= n; i++) { printf ("%d " , ans[i]); } printf ("\n" ); return ; } } for (int i = 1 ; i <= n; i++) { if (!check[0 ][i] && !check[1 ][line+i] && !check[2 ][line+n-i]) { ans[line] = i; check[0 ][i] = check[1 ][line+i] = check[2 ][line+n-i] = 1 ; solve (line+1 ); check[0 ][i] = check[1 ][line+i] = check[2 ][line+n-i] = 0 ; } } } int main () { scanf ("%d" , &n); solve (1 ); printf ("%d\n" , sum); return 0 ; }
洛谷P1019(DFS,暴力)
注意linkstr()函数返回的应该是最小重叠部分,而非最大
注意开头的字符串也要标记使用过一次
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 #include <iostream> #include <algorithm> #include <string> using namespace std;const int MAX_N = 20 + 1 ;int n;int ans = 0 ;char ch;string str[MAX_N]; int used[MAX_N];int linkstr (string str1, string str2) { for (int i = 0 ; i < min ((int )str1.length (), (int )str2.length ()); ++i) { int flag = 1 ; for (int j = i; j >= 0 ; --j) { if (str2[i-j] != str1[str1.length () - j - 1 ]) flag = 0 ; } if (flag) return i + 1 ; } } void dfs (string strnow, int lengthnow) { ans = max (lengthnow, ans); for (int i = 0 ; i < n; ++i) { int len = linkstr (strnow, str[i]); if (used[i] && len) { used[i]--; dfs (str[i], str[i].length () + lengthnow - len); used[i]++; } } } int main () { cin >> n; for (int i = 0 ; i < n; ++i) { cin >> str[i]; used[i] = 2 ; } cin >> ch; for (int i = 0 ; i < n; ++i) { if (str[i][0 ] == ch) { used[i]--; dfs (str[i], str[i].length ()); used[i]++; } } cout << ans << endl; return 0 ; }
洛谷P1101(单向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 #include <cstdio> const int MAX_N = 100 + 1 ;char map[MAX_N][MAX_N];char str[] = "yizhong" ;char ans[MAX_N][MAX_N];int n;void dfs (int x, int y, int now, int dx, int dy) { if (now == 6 ) { int nx = x; int ny = y; ans[nx][ny] = 'g' ; for (int i = 1 ; i <= 6 ; ++i) { nx -= dx; ny -= dy; ans[nx][ny] = str[6 -i]; } } else { int nx = x + dx; int ny = y + dy; if (nx >= 0 && nx < n && ny >= 0 && ny < n && map[nx][ny] == str[now + 1 ]) dfs (nx, ny, now + 1 , dx, dy); } } int main () { scanf ("%d" , &n); for (int i = 0 ; i < n; ++i) { scanf ("%s" , map[i]); for (int j = 0 ; j < n; ++j) { ans[i][j] = '*' ; } } for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < n; ++j) { if (map[i][j] == 'y' ) { for (int k = -1 ; k <= 1 ; ++k) { for (int l = -1 ; l <= 1 ; ++l) { if (!k && !l) continue ; dfs (i, j, 0 , k, l); } } } } } for (int i = 0 ; i < n; ++i) { puts (ans[i]); } return 0 ; }
洛谷P1605(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 #include <cstdio> const int MAX_NM = 5 + 2 ;const int INF = 1e9 ;int map[MAX_NM][MAX_NM];int d[MAX_NM][MAX_NM];int n, m, t;int sx, sy, gx, gy;int ans = 0 ;int dx[] = {1 , 0 , -1 , 0 };int dy[] = {0 , 1 , 0 , -1 };void dfs (int x, int y) { if (x == gx && y == gy) { ans++; return ; } else { for (int i = 0 ; i < 4 ; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx > 0 && nx <= n && ny > 0 && ny <= m && map[nx][ny] != INF && !d[nx][ny]) { d[nx][ny] = 1 ; dfs (nx, ny); d[nx][ny] = 0 ; } } } } int main () { scanf ("%d%d%d" , &n, &m, &t); scanf ("%d%d%d%d" , &sx, &sy, &gx, &gy); for (int i = 0 ; i < t; ++i) { int x, y; scanf ("%d%d" , &x, &y); map[x][y] = INF; } d[sx][sy] = 1 ; dfs (sx, sy); printf ("%d\n" , ans); return 0 ; }
洛谷P1162(BFS求闭合圈)
先把边界预先染成其它颜色
染色时,先染色再push(),避免重复计算
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 #include <cstdio> #include <queue> using namespace std;const int MAX_N = 30 + 1 ;typedef pair<int , int > pr;int n;int map[MAX_N][MAX_N];int dx[] = {1 , -1 , 0 , 0 };int dy[] = {0 , 0 , 1 , -1 };void bfs (int x, int y, int c) { queue<pr> que; que.push (pr (x, y)); while (que.size ()) { pr p = que.front (); que.pop (); map[p.first][p.second] = c; for (int i = 0 ; i < 4 ; ++i) { int nx = p.first + dx[i]; int ny = p.second + dy[i]; if (0 <= nx && nx < n && 0 <= ny && ny < n && map[nx][ny] == 0 ) { map[nx][ny] = c; que.push (pr (nx, ny)); } } } } int main () { scanf ("%d" , &n); for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < n; ++j) { scanf ("%d" , &map[i][j]); } } for (int i = 0 ; i < n; ++i) { if (!map[i][0 ]) bfs (i, 0 , 3 ); if (!map[i][n-1 ]) bfs (i, n-1 , 3 ); if (!map[0 ][i]) bfs (0 , i, 3 ); if (!map[n-1 ][i]) bfs (n-1 , i, 3 ); } for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < n; ++j) { if (map[i][j] == 0 ) { bfs (i, j, 2 ); } } } for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < n; ++j) { if (map[i][j] == 3 ) printf ("0 " ); else printf ("%d " , map[i][j]); } printf ("\n" ); } return 0 ; }
洛谷P1141(BFS,染色)
读错题了orz,不是求从(x, y)所能达到的最远距离,而是从(x, y)所能达到的最多格子数
那么求连通集就好,一个连通集内,所能达到的地方相同
比如在学校是一个连通集,不管是从教学楼出发,还是从寝室出发,最终能到达的地方都是整个学校
%1d这样的输入格式
小技巧,给d赋不同的值,然后映射ret
ret数组不要开小了……
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 #include <cstdio> #include <queue> using namespace std;const int MAX_N = 1e3 + 1 ;int maze[MAX_N][MAX_N];int d[MAX_N][MAX_N];int ret[MAX_N * MAX_N + 1 ];int dx[] = {1 , 0 , -1 , 0 };int dy[] = {0 , 1 , 0 , -1 };int ans = 1 ;int n, m;int num = 1 ;typedef pair<int , int > pr;queue<pr> que; void bfs (int x, int y, int num) { d[x][y] = num; que.push (pr (x, y)); while (!que.empty ()) { pr t = que.front (); que.pop (); int nx, ny; for (int i = 0 ; i < 4 ; ++i) { nx = t.first + dx[i]; ny = t.second + dy[i]; if (0 <= nx && nx < n && 0 <= ny && ny < n && !d[nx][ny] && maze[nx][ny] != maze[t.first][t.second]) { d[nx][ny] = num; ans++; que.push (pr (nx, ny)); } } } ret[num] = ans; ans = 1 ; } int main () { scanf ("%d%d" , &n, &m); for (int i = 0 ; i < n; ++i) for (int j = 0 ; j < n; ++j) scanf ("%1d" , &maze[i][j]); for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < n; ++j) { if (!d[i][j]) bfs (i, j, num++); } } for (int i = 0 ; i < m; ++i) { int a, b; scanf ("%d%d" , &a, &b); printf ("%d\n" , ret[d[a-1 ][b-1 ]]); } return 0 ; }
洛谷P1443(非上下左右移动的BFS)
改变方向数据即可
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 #include <cstdio> #include <queue> #include <utility> using namespace std;const int MAX_MN = 400 + 1 ;typedef pair<int , int > pr;int map[MAX_MN][MAX_MN];int m, n, sx, sy;int dx[] = {2 , 2 , 1 , 1 , -1 , -1 , -2 , -2 };int dy[] = {1 , -1 , 2 , -2 , 2 , -2 , 1 , -1 };void bfs () { queue<pr> que; que.push (pr (sx-1 , sy-1 )); while (que.size ()) { pr p = que.front (); que.pop (); for (int i = 0 ; i < 8 ; ++i) { int nx = p.first + dx[i]; int ny = p.second + dy[i]; if (0 <= nx && nx < m && 0 <= ny && ny < n && map[nx][ny] == -1 ) { map[nx][ny] = map[p.first][p.second] + 1 ; que.push (pr (nx, ny)); } } } } int main () { scanf ("%d%d%d%d" , &m, &n, &sx, &sy); for (int i = 0 ; i < m; ++i) { for (int j = 0 ; j < n; ++j) { map[i][j] = -1 ; } } map[sx-1 ][sy-1 ] = 0 ; bfs (); for (int i = 0 ; i < m; ++i) { for (int j = 0 ; j < n; ++j) { printf ("%-5d" , map[i][j]); } printf ("\n" ); } return 0 ; }
总结 何为搜索?
我接触的第一道搜索题是白书上的部分和问题
。是一道简单的BFS,当时由于对递归的理解不够,导致花了好多天才理解为什么要这么写。到我能真正写出DFS那是更后面的事了。
后来我会熟练地写地图上的搜索了,并天真地以为搜索就是指图的搜索。在一个图中给出入口出口,寻找最短路径或者求连通块便是搜索。我做了很多板子题,并自得其乐。洛谷P1101
,洛谷P1605
,洛谷P1162
,洛谷P1141
。
再后来逐渐接触一些稍微变形点的题,比如三维的啦POJ2251
,像马那样跳跃的啦洛谷P1443
,多点一起的搜索啦FZU2150
,UVA11624
,八皇后相关的啦洛谷P1219
,POJ1321
,路径还原啦POJ3984
,POJ3414
再后来,我就自闭了……因为发现这个时候剩下的题都是没什么思路的,它不是一个地图,我想象不出它的样子,无法把它们套进搜索的模型里。
好在随着时间的流逝,我也逐渐开窍了。懂得了地图只是搜索的一个很直观的表现。搜索是一个状态根据一个规则到达另一份状态,后者再根据同一个规则到达下一份状态,直至搜完所有的可能或者得到目标值,应该也是一种暴力的方法(莽夫的智慧)。而BFS还是DFS只是搜索策略的不同罢了。