本文主要是介绍784 - Maze Exploration(bfs),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:784 - Maze Exploration
题目大意:类似走迷宫, 八个方向走,空格的表示可以走,‘X’不可以走,‘*’是起点。
解题思路:BFS;
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;const int N = 35;
const int M = 85;
int t, k;char maze[N][M];
int visit[N][M];int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
struct node {int x, y;
};
queue<node> q;void bfs(int x, int y) {visit[x][y] = 1;maze[x][y] = '#';node n;n.x = x;n.y = y;q.push(n);while(!q.empty()) {n = q.front();q.pop();for(int i = 0; i < 8; i++) {int x = n.x + dir[i][0];int y = n.y + dir[i][1];if(x >= 0 && x < k && y >= 0 && y < strlen(maze[x])) {if(maze[x][y] == ' ' && !visit[x][y]) {visit[x][y] = 1;maze[x][y] = '#';node n1;n1.x = x;n1.y = y;q.push(n1);}}}}}int main() {scanf("%d%*c", &t);while(t--) {memset(maze, 0, sizeof(maze));memset(visit, 0, sizeof(visit));k = 0;while(gets(maze[k])) {if(maze[k][0] == '_')break;k++;}int i, j;for(i = 0; i < k; i++) {for(j = 0; j < strlen(maze[i]); j++)if(maze[i][j] == '*')break;if(maze[i][j] == '*')break;}bfs(i, j);for(i = 0; i <= k; i++)printf("%s\n", maze[i]);}return 0;
}
这篇关于784 - Maze Exploration(bfs)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!