首页 > 代码库 > Uva 1600 Patrol Robot (BFS 最短路/DFS剪枝)
Uva 1600 Patrol Robot (BFS 最短路/DFS剪枝)
这道题运用的知识点是求最短路的算法。一种方法是利用BFS来求最短路。
需要注意的是，我们要用一个三维数组来表示此状态是否访问过，而不是三维数组。因为相同的坐标可以通过不同的穿墙方式到达。
#include <bits/stdc++.h>using namespace std;struct Node{ int r; int c; int g; int cnt; Node(int r,int c,int g,int cnt):r(r),c(c),g(g),cnt(cnt){}};int visit[30][30][30];int maps[30][30];int m,n,k;int ans;const int dr[]={1,-1,0,0};const int dc[]={0,0,1,-1};int bfs(){ queue<Node> q; q.push(Node(1,1,0,0)); visit[1][1][0] = 1; while(!q.empty()){ Node u = q.front(); q.pop(); int r = u.r; int c = u.c; int cnt1 = u.cnt; if(r == n && c == m) return cnt1; for(int i = 0; i < 4; i++){ int gg = u.g; int r0 = r + dr[i]; int c0 = c + dc[i]; if(r0 < 1 || c0 < 1 || r0 > n || c0 > m) continue; if(maps[r0][c0]) gg++; else gg = 0; if(gg > k || visit[r0][c0][gg])continue; visit[r0][c0][gg] = 1; q.push(Node(r0,c0,gg,cnt1+1)); } } return -1;}int main(){ int T; scanf("%d",&T); while(T--){ memset(visit,0,sizeof(visit)); scanf("%d%d%d",&n,&m,&k); for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= m ; j ++) scanf("%d",&maps[i][j]); printf("%d\n",bfs()); } return 0;}
再一个方法可以用DFS求解。普通的DFS一定会超时。
State[r0][c0][gg] = 1;dfs(r0,c0,gg,cnt+1);State[r0][c0][gg] = 0;
我们把原来的DFS进行一些修改：只有当前节点没有访问或者需要更新值时进行递归。
1 #include <bits/stdc++.h> 2 using namespace std; 3 struct Node{ 4 int r; 5 int c; 6 int g; 7 int cnt; 8 Node(int r,int c,int g,int cnt):r(r),c(c),g(g),cnt(cnt){} 9 };10 int State[30][30][30];11 int maps[30][30];12 int m,n,k;13 int ans;14 const int dr[]={1,-1,0,0};15 const int dc[]={0,0,1,-1};16 void dfs(int r,int c,int g,int cnt){17 if(r == n && c == m)18 ans = min(ans,cnt);19 20 for(int i = 0; i < 4; i++){21 int r0 = r + dr[i];22 int c0 = c + dc[i];23 int gg = g;24 if(r0 < 1 || c0 < 1 || r0 > n || c0 > m) continue;25 if(maps[r0][c0]) gg++;26 else gg = 0;27 if(gg > k)continue;28 if((State[r0][c0][gg] < 0 || State[r0][c0][gg] > cnt + 1) && gg <= k ){29 State[r0][c0][gg] = cnt + 1;30 dfs(r0,c0,gg,cnt+1);31 }32 }33 }34 int main(){35 int T; 36 scanf("%d",&T); 37 while(T--){ 38 memset(State,-1,sizeof(State)); 39 ans = 1 << 30; 40 scanf("%d%d%d",&n,&m,&k); 41 for(int i = 1 ; i <= n ; i++) 42 for(int j = 1 ; j <= m ; j ++) 43 scanf("%d",&maps[i][j]); 44 dfs(1,1,0,0);45 if(ans != 1 << 30)printf("%d\n",ans);46 else printf("-1\n"); 47 } 48 return 0;49 }
Uva 1600 Patrol Robot (BFS 最短路/DFS剪枝)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。