首页 > 代码库 > 搜索进阶题
搜索进阶题
1.http://acm.hdu.edu.cn/showproblem.php?pid=1254
分析：由于箱子每次都只能推，而不能拉，所以我们知道，每次往方向 i 推的时候，人必然会站在一个确切的位置 p 。所以我们在每次推箱子的时候先bfs求出人是否可以到达 p 位置。若可以到达 p ，则往 p 的对面的推动一格，否则判断下一个方向。直到推到目标位置为止。然后我们得到下面的代码：
1 //First Edit Time: 2014-11-02 17:06 2 //Last Edit Time: 2014-11-02 18:20 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 using namespace std; 7 8 struct Pos 9 { 10 int bx, by; 11 int px, py; 12 int step; 13 }Box, Person; 14 15 int map[10][10], n, m; 16 bool used[10][10][10][10]; 17 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 18 bool visited[10][10]; 19 20 bool Judge_Person (Pos a) 21 { 22 if(a.px<0 || a.px>m-1 || a.py<0 || a.py>n-1 || visited[a.px][a.py] 23 || map[a.px][a.py]==1 || (a.px==Box.bx && a.py==Box.by)) 24 return false; 25 return true; 26 } 27 28 bool Judge_Box (Pos a) 29 { 30 if(a.bx<0 || a.bx>m-1 || a.by<0 || a.by>n-1 || used[a.bx][a.by][Person.px][Person.py] || map[a.bx][a.by]==1) 31 return false; 32 return true; 33 } 34 35 Pos Find_p (Pos a, int i) 36 { 37 Pos P = a; 38 if (i==0) 39 { 40 P.px = a.bx + dir[1][0]; 41 P.py = a.by + dir[1][1]; 42 } 43 else if (i==1) 44 { 45 P.px = a.bx + dir[0][0]; 46 P.py = a.by + dir[0][1]; 47 } 48 else if (i==2) 49 { 50 P.px = a.bx + dir[3][0]; 51 P.py = a.by + dir[3][1]; 52 } 53 else if (i==3) 54 { 55 P.px = a.bx + dir[2][0]; 56 P.py = a.by + dir[2][1]; 57 } 58 return P; 59 } 60 61 // 62 bool bfs_person (Pos a) 63 { 64 memset (visited, 0, sizeof visited); 65 if (!Judge_Person (a)) return false; 66 67 Pos Pre, Cur; 68 queue <Pos> Q; 69 visited[Person.px][Person.py] = true; 70 71 Q.push (Person); 72 while (!Q.empty()) 73 { 74 Pre = Q.front(); 75 Q.pop(); 76 for (int i=0; i<4; i++) 77 { 78 Cur.px = Pre.px + dir[i][0]; 79 Cur.py = Pre.py + dir[i][1]; 80 if (Judge_Person (Cur)) 81 { 82 visited[Cur.px][Cur.py] = true; 83 if (Cur.px==a.px && Cur.py==a.py) 84 return true; 85 Q.push (Cur); 86 } 87 } 88 } 89 return false; 90 } 91 92 int bfs_box () 93 { 94 Pos Pre, Cur, P; 95 queue <Pos> Q; 96 memset (used, 0, sizeof used); 97 98 used[Box.bx][Box.by][Person.px][Person.py] = true; 99 Q.push (Box);100 while (!Q.empty ())101 {102 Pre = Q.front ();103 Q.pop();104 for (int i=0; i<4; i++)105 {106 Box = Pre;107 108 //找到推箱子的位置109 P = Find_p (Pre, i);110 111 if (bfs_person (P))112 {113 Cur = Pre;114 Person = P;115 Cur.bx += dir[i][0];116 Cur.by += dir[i][1];117 Cur.step += 1;118 if (Judge_Box (Cur))119 {120 used[Cur.bx][Cur.by][Person.px][Person.py] = true;121 if (map[Cur.bx][Cur.by]==3)122 return Cur.step;123 Q.push (Cur);124 }125 }126 }127 }128 return -1;129 }130 131 int main ()132 {133 int t;134 freopen ("test.in","r",stdin);135 scanf ("%d",&t);136 while (t--)137 {138 scanf ("%d%d",&m, &n);139 for (int i=0; i<m; i++)140 for (int j=0; j<n; j++)141 {142 scanf ("%d",map[i]+j);143 if (map[i][j]==2)144 Box.bx=i, Box.by=j, Box.step=0;145 else if (map[i][j]==4)146 Person.px = i,Person.py = j;147 }148 int ans = bfs_box ();149 printf ("%d\n",ans);150 }151 return 0;152 }
然后我就这样一直WA到死。后来问了学长才知道，其实我没有考虑到另一种情况：
1
5 3
0 0 0
0 0 0
0 2 0
1 4 1
1 3 1
在上面这种情况下，以上代码得到的答案是-1，因为上面的程序一开始就访问了他本应该去的位置 p ，导致最后要用到 p 的时候得到 p 不可到达的错误信息而是答案出错。
改正之后的代码：
1 //First Edit Time: 2014-11-02 17:06 2 //Last Edit Time: 2014-11-02 18:20 3 #include <cstdio> 4 #include <cstring> 5 #include <queue> 6 using namespace std; 7 8 struct Pos 9 { 10 int bx, by; 11 int px, py; 12 int step; 13 }Box, Person; 14 15 int map[10][10], n, m; 16 bool used[10][10][10][10]; 17 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 18 bool visited[10][10]; 19 20 bool Judge_Person (Pos a) 21 { 22 if(a.px<0 || a.px>m-1 || a.py<0 || a.py>n-1 || visited[a.px][a.py] 23 || map[a.px][a.py]==1 || (a.px==Box.bx && a.py==Box.by)) 24 return false; 25 return true; 26 } 27 28 bool Judge_Box (Pos a) 29 { 30 if(a.bx<0 || a.bx>m-1 || a.by<0 || a.by>n-1 || used[a.bx][a.by][Person.px][Person.py] || map[a.bx][a.by]==1) 31 return false; 32 return true; 33 } 34 35 Pos Find_p (Pos a, int i) 36 { 37 Pos P = a; 38 if (i==0) 39 { 40 P.px = a.bx + dir[1][0]; 41 P.py = a.by + dir[1][1]; 42 } 43 else if (i==1) 44 { 45 P.px = a.bx + dir[0][0]; 46 P.py = a.by + dir[0][1]; 47 } 48 else if (i==2) 49 { 50 P.px = a.bx + dir[3][0]; 51 P.py = a.by + dir[3][1]; 52 } 53 else if (i==3) 54 { 55 P.px = a.bx + dir[2][0]; 56 P.py = a.by + dir[2][1]; 57 } 58 return P; 59 } 60 61 // 62 bool bfs_person (Pos a) 63 { 64 memset (visited, 0, sizeof visited); 65 if (!Judge_Person (a)) return false; 66 if (a.px==Person.px && a.py==Person.py) //改正之处。就是把那种情况特判了一下； 67 return true; 68 Pos Pre, Cur; 69 queue <Pos> Q; 70 visited[Person.px][Person.py] = true; 71 72 Q.push (Person); 73 while (!Q.empty()) 74 { 75 Pre = Q.front(); 76 Q.pop(); 77 for (int i=0; i<4; i++) 78 { 79 Cur.px = Pre.px + dir[i][0]; 80 Cur.py = Pre.py + dir[i][1]; 81 if (Judge_Person (Cur)) 82 { 83 visited[Cur.px][Cur.py] = true; 84 if (Cur.px==a.px && Cur.py==a.py) 85 return true; 86 Q.push (Cur); 87 } 88 } 89 } 90 return false; 91 } 92 93 int bfs_box () 94 { 95 Pos Pre, Cur, P; 96 queue <Pos> Q; 97 memset (used, 0, sizeof used); 98 99 used[Box.bx][Box.by][Person.px][Person.py] = true;100 Q.push (Box);101 while (!Q.empty ())102 {103 Pre = Q.front ();104 Q.pop();105 // printf ("Box:(%d, %d) ---- %d\n",Pre.bx+1, Pre.by+1, Pre.step);106 for (int i=0; i<4; i++)107 {108 Box = Pre;109 110 //找到推箱子的位置111 P = Find_p (Pre, i);112 // printf ("Person:(%d,%d)\n",P.px+1,P.py+1);113 if (bfs_person (P))114 {115 Cur = Pre;116 Person = P;117 Cur.bx += dir[i][0];118 Cur.by += dir[i][1];119 Cur.step += 1;120 // printf ("Goto:(%d, %d)\n",Cur.bx+1, Cur.by+1);121 if (Judge_Box (Cur))122 {123 used[Cur.bx][Cur.by][Person.px][Person.py] = true;124 if (map[Cur.bx][Cur.by]==3)125 return Cur.step;126 Q.push (Cur);127 }128 }129 }130 }131 return -1;132 }133 134 int main ()135 {136 int t;137 freopen ("test.in","r",stdin);138 scanf ("%d",&t);139 while (t--)140 {141 scanf ("%d%d",&m, &n);142 for (int i=0; i<m; i++)143 for (int j=0; j<n; j++)144 {145 scanf ("%d",map[i]+j);146 if (map[i][j]==2)147 Box.bx=i, Box.by=j, Box.step=0;148 else if (map[i][j]==4)149 Person.px = i,Person.py = j;150 }151 int ans = bfs_box ();152 printf ("%d\n",ans);153 }154 return 0;155 }
搜索进阶题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。