首页 > 代码库 > 搜索基础题
搜索基础题
1.http://acm.hdu.edu.cn/showproblem.php?pid=1312
题意：在一个仅有红黑格子组成的矩形中，一个人只能走上下左右相邻黑色格子，问从起点开始共能走多少个格子？
’#‘：红色格子
’.‘： 黑色格子；
’@‘：起点
BFS 和 DFS 都可以遍历所有走的点，每次走过一点时，计数++即可；
2.http://acm.hdu.edu.cn/showproblem.php?pid=1728
由题可知，在限制转弯数量的前提下 能够从一点走到另一个点即可；BFS 和 DFS都能求出解。我 DFS 还没实现
需要注意：1.点坐标是从 1 开始的。
2.最短的路径可能不满足转弯数的限制。
3.起点与终点重合。
超内存代码：还没找到原因。
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 #define N 105 6 7 struct Pos 8 { 9 int x, y;10 int turn;11 int dire;12 }S, E;13 char map[N][N];14 bool used[N][N][12][4];15 int dir[][2]={1,0, -1,0, 0,1, 0,-1};16 int n, m, k;17 18 bool Judge (Pos s)19 {20 if (s.x>=1 && s.x<=m && s.y>=1 && s.y<=n && map[s.x][s.y]==‘.‘ && !used[s.x][s.y][S.turn][S.dire] && s.turn <= k)21 return true;22 return false;23 }24 25 bool bfs ()26 {27 Pos Pre, Cur;28 queue <Pos> Q;29 while (!Q.empty ()) Q.pop();30 memset (used, 0, sizeof used);31 32 S.dire = -1;33 S.turn = 0;34 used[S.x][S.y][S.turn][S.dire] = true;35 Q.push (S);36 while (!Q.empty ())37 {38 Pre = Q.front ();39 Cur = Pre;40 Q.pop();41 if (Cur.x==E.x && Cur.y==E.y)42 return true;43 for(int i=0; i<4; i++)44 {45 Cur.x = Pre.x + dir[i][0];46 Cur.y = Pre.y + dir[i][1];47 Cur.turn = Pre.turn;48 Cur.dire = i;49 if (Cur.dire != Pre.dire && Pre.dire !=-1)50 Cur.turn++;51 if (Judge (Cur))52 {53 used[Cur.x][Cur.y][Cur.turn][Cur.dire] = true;54 Q.push (Cur);55 }56 }57 }58 return false;59 }60 61 int main ()62 {63 int t;64 // freopen ("test.txt","r",stdin);65 scanf ("%d",&t);66 while (t--)67 {68 scanf ("%d%d",&m, &n);69 for (int i=1; i<=m; i++)70 for (int j=1; j<=n; j++)71 scanf (" %c", map[i]+j);72 scanf ("%d%d%d%d%d",&k, &S.y, &S.x, &E.y, &E.x);73 74 puts ((bfs ()?"yes":"no"));75 }76 return 0;77 }
1.http://acm.hdu.edu.cn/showproblem.php?pid=1010；
题意：在一个矩形的迷宫里面， 问是否可以恰好在 给定的时间点 走到出口。
‘X‘：墙壁；
’S‘：起点；
‘D‘：出口；
’.‘: 空地。
这道题，是问你是否有解，不是要求最优解，所以可以用DFS深度搜索， 奇偶性剪枝+路径剪枝优化时间防TLE。如果硬是要用BFS按理来说应该是可以求出结果的，不过我BFS一直WA，一直想不通。留着以后进步了再斟酌。
DFS代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 using namespace std; 5 6 int n, m, t, ex, ey; 7 char map[10][10]; 8 bool visit[10][10], flag; 9 int dir[][2]={1,0, -1,0, 0,1, 0,-1};10 11 void dfs (int x, int y, int cnt)12 {13 if (x<0 || x>n-1 || y<0 || y>m-1) return;14 if (flag || cnt > t) return;15 if (x==ex && y==ey)16 {17 if (cnt == t)18 flag = true;19 return;20 }21 for (int i=0; i<4; i++)22 {23 int xx = x + dir[i][0];24 int yy = y + dir[i][1];25 if (map[xx][yy]==‘X‘ || visit[xx][yy]) continue;26 visit[xx][yy] = true;27 dfs (xx, yy, cnt+1);28 if (flag) return;29 visit[xx][yy] = false;30 }31 }32 int main ()33 {34 // freopen ("test.txt","r",stdin);35 while (~scanf ("%d%d%d",&n, &m, &t) && n+m+t)36 {37 int wall=0, sx, sy;38 for (int i=0; i<n; i++)39 for (int j=0; j<m; j++)40 {41 scanf (" %c",map[i]+j);42 if (map[i][j] == ‘S‘)43 {44 sx = i; sy = j;45 }46 else if (map[i][j]==‘D‘)47 {48 ex = i; ey = j;49 }50 else if (map[i][j]==‘X‘)51 wall++;52 }53 //路径剪枝54 if (n*m-wall < t)55 {56 puts ("NO");57 continue;58 }59 //奇偶性剪枝60 int tmp = fabs (sx-ex) + fabs (sy-ey);61 if ((t - tmp) & 1)62 {63 puts ("NO");64 continue;65 }66 memset (visit, 0, sizeof visit);67 flag = false;68 visit[sx][sy] = true;69 dfs(sx, sy, 0);70 puts ((flag?"YES":"NO"));71 }72 return 0;73 }
搜索基础题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。