胖胖的牛牛

2023-10-20 03:08

文章标签 牛牛胖胖的

本文主要是介绍胖胖的牛牛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址

链接：https://ac.nowcoder.com/acm/problem/208246
来源：牛客网

题目

每逢佳节胖三斤，牛牛在过去的节日里长胖了，连拐弯都困难，甚至会卡在门上，所以他很讨厌拐弯。给你一个N*N（2≤N≤100）的方格中，‘x’表示障碍，‘.’表示没有障碍（可以走），牛牛可以从一个格子走到他相邻的四个格子，但是不能走出这些格子。问牛牛从A点到B点最少需要转90度的弯几次。

思路：
①把最少拐弯次数看成最短路问题，用求最短路的方法求就行了
②注意到达一个的拐弯次数可能一样，但由于方向问题，会导致到终点的拐弯次数是不一样的，而且一个点最多被上下或者左右两种方向的最短拐弯路径经过，所以要允许一个点至少被2次以同样的最短拐弯数走过。

方法1
dfs+记忆化+回溯

#include<bits/stdc++.h>
using namespace std;
#define ios std::ios::sync_with_stdio(false);
char graph[120][120];
int vis[120][120];
int flag[120][120];
int ax,ay,bx,by;
int run[5][2] = {{1,1},{1,0},{-1,0},{0,1},{0,-1}};
int n;
int sum = 0x3f3f3f3f;
bool right_index(int x,int y){return 0<= x  && x < n && 0 <= y && y < n ;
}void dfs(int x,int y,int time,int statue){if(graph[x][y] == 'B')sum = min(sum,time);if(vis[x][y] && time > vis[x][y])return ;//cout << x << " " << y << endl;vis[x][y] = time;int x1,y1;for(int i = 1;i <= 4;i++){x1 = x + run[i][0];y1 = y + run[i][1];if(!right_index(x1,y1) || graph[x1][y1] == 'x'|| flag[x1][y1])continue;if(statue == -1 || (statue - 1)/2 == (i-1)/2){//如果是起点，或者同向flag[x1][y1] = 1;dfs(x1,y1,time,i);flag[x1][y1] = 0;}else{flag[x1][y1] = 1;dfs(x1,y1,time+1,i);flag[x1][y1] = 0;}}return ;
}int main(){ioscin >> n;for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){cin >> graph[i][j];}}for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){if(graph[i][j] == 'A')ax = i,ay = j;}}dfs(ax,ay,0,-1);if(sum >= 0x3f3f3f3f)cout << -1 ;else cout << sum <<endl;return 0;
}

方法2
dijsktra + 优先队列

#include<bits/stdc++.h>
using namespace std;
const int MAX = 200;
char graph[MAX][MAX];
int vis[MAX][MAX];
bool flag[MAX][MAX];
int ax,ay,bx,by;
int run[5][2] = {{1,1},{0,1},{1,0},{-1,0},{0,-1}};
int n;struct point{int x, y,w,to,cnt;//x,y，转弯次数，方向，那一次入队bool operator < (const point &ty) const {if(w == ty.w)return cnt < ty.cnt;return w > ty.w;}
};priority_queue<point> q;bool right_index(int x,int y){return 0<= x  && x < n && 0 <= y && y < n;
}void bfs(int x,int y){point t,t1;int x1,y1; int count = 0;t.x = x;t.y = y;t.to = t.w = t.cnt = 0;vis[x][y] = 0;q.push(t);while(!q.empty()){t = q.top();q.pop();flag[t.x][t.y] = 1;count++;for(int i = 1;i <=4;i++){x1 = t.x + run[i][0];y1 = t.y + run[i][1];if(!right_index(x1,y1) || flag[x1][y1] || graph[x1][y1] == 'x' || vis[x1][y1] < vis[t.x][t.y])continue;//cout << x1 << " " << y1 << " " << t.to << " " << i << endl;if(!t.to || t.to + i == 5 || t.to == i)t1.w = vis[x1][y1] =  vis[t.x][t.y];else t1.w = vis[x1][y1] = min(vis[x1][y1],vis[t.x][t.y] + 1) ;t1.to = i;t1.x = x1;t1.y = y1;t1.cnt = count;q.push(t1);}}return ;
}int main(){memset(vis,0x3f,sizeof(vis));cin >> n;for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){cin >> graph[i][j];}}for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){if(graph[i][j] == 'A')ax = i,ay = j;if(graph[i][j] == 'B')bx = i,by = j;}}bfs(ax,ay);/*for(int i = 0;i < n;i++){for(int j = 0;j < n;j++)cout << vis[i][j] << " ";cout << endl;}*/if(vis[bx][by] >= 0x3f3f3f3f)cout << -1 ;else cout << vis[bx][by] << endl;//system("pause");return 0;
}