uva1600(最短路bfs &dfs)

xiaoxiao2021-02-28  121

题目链接 https://vjudge.net/problem/UVA-1600(uva 1600 点击打开题目链接)

思路:bfs或dfs遍历

分析:如果没有题目中的最多一次可以跨过k个障碍,而是最多 一次就只能跨过一个障碍,那这道题就是比较简单的一道题了。加了那个条件后就不知道怎么处理了,看了别人的题解,好不容易理解了,自己敲的代码却总是错的,一个下午都没看出哪里有bug,心塞啊。。。。加上那条件后有的用来三维数组来做的,也有仍然用二维数组的,都看了一下,只能说佩服佩服。

代码: bfs(二维数组)

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct point{ //step记步数,k记允许一次穿过的障碍数 int x,y,step,k; point(int x,int y,int step,int k):x(x),y(y),step(step),k(k){}; }; int T,n,m,kk; int map[30][30]; bool vis[30][30]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int BFS() { memset(vis,false,sizeof(vis)); queue<point> q; q.push(point(0,0,0,kk)); int x,y; while(q.size()){ x=q.front().x,y=q.front().y; //判断条件,到了右下角的点就返回步数 if(x==m-1&&y==n-1) return q.front().step; vis[x][y]=true;//是标记走过了没吗 for(int i=0;i<4;i++){ int mx=dx[i]+x,my=dy[i]+y; if(mx<0||mx>=m||my<0||my>=n||vis[mx][my]) continue; if(map[mx][my]==0) q.push(point(mx,my,q.front().step+1,kk));//如果是没有障碍的点,k要变回原来的数 if(map[mx][my]==1&&q.front().k>0) //否则,k-1 q.push(point(mx,my,q.front().step+1,q.front().k-1)); } q.pop(); } return -1; } int main() { while(cin>>T){ while(T--){ scanf("%d%d%d",&m,&n,&kk); for(int i=0;i<m;i++){ for(int j=0;j<n;j++) cin>>map[i][j]; } cout<<BFS()<<endl; } } return 0; }

bfs(三维数组)

#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <deque> #include <map> #include <set> #include <iterator> using namespace std; const int maxn = 30; struct node { int x,y,step,k; //k是当前穿过了多少障碍 node(int x,int y,int step,int kk):x(x),y(y),step(step),k(kk){} }; int arr[maxn][maxn][maxn]; int brr[maxn][maxn]; int t,n,m,k; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int bfs() { queue<node> q; while(!q.empty()) q.pop(); q.push(node(1,1,0,0)); while(!q.empty()) { node now = q.front(); q.pop(); int x = now.x; int y = now.y; int sstep = now.step; //判断条件,跳出bfs if(x == n && y == m) return sstep; for(int i = 0;i < 4;i++) { int kk = now.k; int nx = x + dx[i]; int ny = y + dy[i]; if(nx < 1 || nx > n || ny > m || ny < 1) continue; if(brr[nx][ny]) kk++; else kk = 0; //如果当前的障碍已经比可以穿过的大了或者已经经过这种方式了 if(kk > k || arr[nx][ny][kk] == 1) continue; arr[nx][ny][kk] = 1; q.push(node(nx,ny,sstep+1,kk)); } } return -1; } int main() { scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&k); memset(arr,0,sizeof(arr)); memset(brr,0,sizeof(brr)); for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { scanf("%d%",&brr[i][j]); } } printf("%d\n",bfs()); } } 注意:二维数组里放入队列时是可以穿过的障碍数减减,而三维数组里用一个变量标记穿过的障碍数,遇到障碍就加加,然后和允许穿过的障碍数做比较。自己总结的bfs的套路,自己明白,不知道别人看不看的明白 int bfs() { 定义变量,标记队列的首元素 while(!q.empty()) { 删除队列的首元素 判断返回条件(跳出bfs的) for(int i = 0....4) { 4个方向遍历 判断是否越界,是否可以通过 { 可以的话,放入队列 } } } }

代码: (dfs)

#include <iostream> #include <algorithm> #include <string> #include <cstring> #include <cstdio> using namespace std; struct node { int r,c,g,cnt; node(int r,int c,int g,int cnt):r(r),c(c),g(g),cnt(cnt){} }; int state[30][30][30]; int maps[30][30]; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int n,m,k,ans; void dfs(int r,int c,int g,int cnt) { //判断条件,更新 if(r == n && c == m) ans = min(ans,cnt); for(int i = 0;i < 4;i++) { int r0 = r + dx[i]; int c0 = c + dy[i]; int gg = g; if(r0 < 1 || r0 > n || c0 < 1 || c0 > m) continue; if(maps[r0][c0]) gg++; else gg = 0; if(gg > k) continue; //判断条件 if((state[r0][c0][gg] < 0 || state[r0][c0][gg] > cnt+1) && gg <= k) { state[r0][c0][gg] = cnt + 1; dfs(r0,c0,gg,cnt+1); } } } int main() { int t; scanf("%d",&t); while(t--) { ans = 1 << 30; scanf("%d%d%d",&n,&m,&k); memset(state,-1,sizeof(state)); memset(maps,0,sizeof(maps)); for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) scanf("%d",&maps[i][j]); } dfs(1,1,0,0); if(ans != 1 << 30) printf("%d\n",ans); else printf("-1\n"); } } 感觉两个基础的搜索自己就卡在判断条件上了,怎么想自己都想不出来,心塞,还是多练吧。
转载请注明原文地址: https://www.6miu.com/read-34314.html

最新回复(0)