微信网站特点,百度作文网站,中国设计网官网首页,wordpress 分类 如何修改正题 题目大意 n∗mn*mn∗m的地图#xff0c;每个格子有限制。是障碍的话就不可以到#xff0c;如果不是就会要求在这个格子不可以像上下左右其中一个方位走。求最少拐弯次数。 解题思路
就是bfs#xff0c;之前写过类似的#xff0c;详见#xff1a;https://blog.csdn.n…正题 题目大意
n∗mn*mn∗m的地图每个格子有限制。是障碍的话就不可以到如果不是就会要求在这个格子不可以像上下左右其中一个方位走。求最少拐弯次数。 解题思路
就是bfs之前写过类似的详见https://blog.csdn.net/Mr_wuyongcong/article/details/78755411 code
#includecstdio
#includequeue
#includealgorithm
#includeiostream
#define N 510
using namespace std;
const int dx[5]{0,-1,0,1,0},dy[5]{0,0,-1,0,1};
struct node{int x,y,w;
};
queuenode q;
int a[N][N],path[N][N],n,m;
char c;
int bfs()
{q.push((node){1,1,-1});while(!q.empty()){int xq.front().x,yq.front().y,wq.front().w;q.pop();for(int k1;k4;k){int dis1;while(xdx[k]*disnxdx[k]*dis0ydy[k]*dismydy[k]*dis0a[xdx[k]*(dis-1)][ydy[k]*(dis-1)]!ka[xdx[k]*dis][ydy[k]*dis])//判断的是否可行{if(!path[xdx[k]*dis][ydy[k]*dis])//已经走过{q.push((node){xdx[k]*dis,ydy[k]*dis,w1});path[xdx[k]*dis][ydy[k]*dis]1;//标记if(xdx[k]*disnydy[k]*dism)//到达return w1;}dis;}}}return -1;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)for(int j1;jm;j){cinc;if(cU) a[i][j]1;else if (cD) a[i][j]3;else if (cL) a[i][j]2;else if (cR) a[i][j]4;}//输入a[n][m]4;//防止终点是障碍物int ansbfs();if(ans-1) printf(No Solution);else printf(%d,ans);
}
