【搜索】JZOJ_5793 小s练跑步

本文主要是介绍【搜索】JZOJ_5793 小s练跑步，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

一个$N\times M$的矩阵，上面有些字母，每个字母代表了不能往那个方向走，如果上面是$S$，那么走到那里就不能动了，求从（1，1）走到（N，M）的最少拐弯次数。

思路

广搜。
一个方向一个方向的拓展，直到不能走为止。

代码

#include<queue>
#include<cstdio>
using namespace std;const int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};
int N, M;
int a[501][501], v[501][501];
char c[501];
struct node{int x, y, s;
};bool check(int x, int y) {return x <= N && x >= 1 && y <= M && y >= 1 && a[x][y] != 5;
}void bfs() {queue<node> q;q.push((node){1, 1, -1});v[1][1] = 1;while (q.size()) {node h = q.front();q.pop();if (a[h.x][h.y] == 5) continue;for (int i = 1; i <= 4; i++) {if (a[h.x][h.y] == i) continue;for (int k = 0, xx, yy; ;) {//一直拓展k++;xx = h.x + dx[i] * k; yy = h.y + dy[i] * k;if (!check(xx, yy) || a[xx - dx[i]][yy - dy[i]] == i) break;//判断是否能到达if (v[xx][yy]) continue;v[xx][yy] = 1;q.push((node){xx, yy, h.s + 1});if (xx == N && yy == M) {printf("%d", h.s + 1);return;}}}}printf("No Solution");return;
}int main() {scanf("%d %d", &N, &M);for (int i = 1; i <= N; i++) {scanf("%s", c);for (int j = 0; j < M; j++)if (c[j] == 'U') a[i][j + 1] = 1;else if (c[j] == 'D') a[i][j + 1] = 2;else if (c[j] == 'L') a[i][j + 1] = 3;else if (c[j] == 'R') a[i][j + 1] = 4; else a[i][j + 1] = 5;}a[N][M] = 0;//如果终点上面是S的话也要走bfs();
}

这篇关于【搜索】JZOJ_5793 小s练跑步的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---