再解炸弹人--广度搜索和深度搜索

本文主要是介绍再解炸弹人--广度搜索和深度搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

再解炸弹人

要求

之前炸弹人通过枚举统计每个点消灭敌人数，包括了小人不能直接到达的位置，现在要求小人从（3，3）位置开始，有敌人的地方小人不能通过，统计消灭敌人数。

思路

先使用广度优先搜索或者深度优先搜索找出小人可以通过的点，再统计这些点消灭敌人数

bfs代码

#include <stdio.h>#define N 13
#define M 13char a[13][13] = {"#############","#GG.GGG#GGG.#","###.#G#G#G#G#","#.......#..G#","#G#.###.#G#G#","#GG.GGG.#.GG#","#G#.#G#.#.#.#","##G...G.....#","#G#.#G###.#G#","#...G#GGG.GG#","#G#.#G#G#.#G#","#GG.GGG#G.GG#","#############"};int b[13][13] = {0};struct node 
{int x;int y;
};struct node que[401];  // 地图大小不超过20*20
int head = 0, tail = 0;void enqueue(struct node p) {que[tail] = p;tail++;
}struct node dequeue() {head++;return que[head-1];
}int is_empty() {return head == tail;
}void print_a() {for (int i = 0; i < N; ++i){for (int j = 0; j < M; ++j){printf("%c ", a[i][j]);}printf("\n");}printf("\n");
}void print_b() {for (int i = 0; i < N; ++i){for (int j = 0; j < M; ++j){printf("%d ", b[i][j]);}printf("\n");}printf("\n");
}int main() 
{int i, j;struct node p = {3, 3}; // 小人所在位置enqueue(p);a[p.x][p.y] = '2'; // 小人到达点标记为2while(!is_empty()) {p = dequeue();// 统计此处安放炸弹消灭敌人数i = p.x;j = p.y;while(a[i][j] != '#') {  //rightj++;if(a[i][j] == 'G') {b[p.x][p.y]++;}}i = p.x;j = p.y;while(a[i][j] != '#') {  //downi++;if(a[i][j] == 'G') {b[p.x][p.y]++;}}i = p.x;j = p.y;while(a[i][j] != '#') {  //leftj--;if(a[i][j] == 'G') {b[p.x][p.y]++;}}i = p.x;j = p.y;while(a[i][j] != '#') {  // upi--;if(a[i][j] == 'G') {b[p.x][p.y]++;}}// bfs 搜索小人可以到达的点if (a[p.x][p.y+1] == '.') {struct node temp = {p.x, p.y+1};enqueue(temp);a[p.x][p.y+1] = '2';}if (a[p.x+1][p.y] == '.') {struct node temp = {p.x+1, p.y};enqueue(temp);a[p.x+1][p.y] = '2';}if (a[p.x][p.y-1] == '.') {struct node temp = {p.x, p.y-1};enqueue(temp);a[p.x][p.y-1] = '2';}if (a[p.x-1][p.y] == '.') {struct node temp = {p.x-1, p.y};enqueue(temp);a[p.x-1][p.y] = '2';}}print_a();print_b();return 0;
}

dfs代码

#include <stdio.h>#define N 13
#define M 13char a[13][13] = {"#############","#GG.GGG#GGG.#","###.#G#G#G#G#","#.......#..G#","#G#.###.#G#G#","#GG.GGG.#.GG#","#G#.#G#.#.#.#","##G...G.....#","#G#.#G###.#G#","#...G#GGG.GG#","#G#.#G#G#.#G#","#GG.GGG#G.GG#","#############"};int b[13][13] = {0};struct node 
{int x;int y;
};struct node stack[41];
int top = 0;void push(struct node p) {stack[top] = p;top++;
}struct node pop() {top--;return stack[top];
}int is_empty() {return top == 0;
}void print_a() {for (int i = 0; i < N; ++i){for (int j = 0; j < M; ++j){printf("%c ", a[i][j]);}printf("\n");}printf("\n");
}void print_b() {for (int i = 0; i < N; ++i){for (int j = 0; j < M; ++j){printf("%d ", b[i][j]);}printf("\n");}printf("\n");
}int main() 
{int i, j;struct node p = {3, 3}; // 小人所在位置push(p);a[p.x][p.y] = '2';while(!is_empty()) {p = pop();// 统计此处安放炸弹消灭敌人数i = p.x;j = p.y;while(a[i][j] != '#') {  //rightj++;if(a[i][j] == 'G') {b[p.x][p.y]++;}}i = p.x;j = p.y;while(a[i][j] != '#') {  //downi++;if(a[i][j] == 'G') {b[p.x][p.y]++;}}i = p.x;j = p.y;while(a[i][j] != '#') {  //leftj--;if(a[i][j] == 'G') {b[p.x][p.y]++;}}i = p.x;j = p.y;while(a[i][j] != '#') {  // upi--;if(a[i][j] == 'G') {b[p.x][p.y]++;}}// bfs 搜索小人可以到达的点if (a[p.x][p.y+1] == '.') {struct node temp = {p.x, p.y+1};push(temp);a[p.x][p.y+1] = '2';}if (a[p.x+1][p.y] == '.') {struct node temp = {p.x+1, p.y};push(temp);a[p.x+1][p.y] = '2';}if (a[p.x][p.y-1] == '.') {struct node temp = {p.x, p.y-1};push(temp);a[p.x][p.y-1] = '2';}if (a[p.x-1][p.y] == '.') {struct node temp = {p.x-1, p.y};push(temp);a[p.x-1][p.y] = '2';}}print_a();print_b();return 0;
}

结果

# # # # # # # # # # # # #
# G G 2 G G G # G G G . #
# # # 2 # G # G # G # G #
# 2 2 2 2 2 2 2 # . . G #
# G # 2 # # # 2 # G # G #
# G G 2 G G G 2 # 2 G G #
# G # 2 # G # 2 # 2 # 2 #
# # G 2 2 2 G 2 2 2 2 2 #
# G # 2 # G # # # 2 # G #
# 2 2 2 G # G G G 2 G G #
# G # 2 # G # G # 2 # G #
# G G 2 G G G # G 2 G G #
# # # # # # # # # # # # #0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 5 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 3 0 0 0 2 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 5 0 0 0 6 0 5 0 0 0
0 0 0 0 0 0 0 1 0 3 0 8 0
0 0 0 2 2 5 0 3 2 5 2 10 0
0 0 0 0 0 0 0 0 0 3 0 0 0
0 4 1 1 0 0 0 0 0 8 0 0 0
0 0 0 0 0 0 0 0 0 3 0 0 0
0 0 0 5 0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0

python 代码

N = 13
M = 13a  =   ["#############","#GG.GGG#GGG.#","###.#G#G#G#G#","#.......#..G#","#G#.###.#G#G#","#GG.GGG.#.GG#","#G#.#G#.#.#.#","##G...G.....#","#G#.#G###.#G#","#...G#GGG.GG#","#G#.#G#G#.#G#","#GG.GGG#G.GG#","#############"]b = [([0] * N) for i in range(N)]q = []
s = []def mprint(x):for i in range(N):print(x[i])def marking(a, i, j):text = a[i]new = text[:j] + "2" + text[j+1:]a[i] = newdef bfs(i, j):q.append((i, j))marking(a, i, j)while len(q) != 0:i, j = q.pop(0)x = iy = jwhile a[x][y] != '#':  # righty = y + 1if a[x][y] == 'G':b[i][j] = b[i][j] + 1x = iy = jwhile a[x][y] != '#':  # downx = x + 1if a[x][y] == 'G':b[i][j] = b[i][j] + 1x = iy = jwhile a[x][y] != '#':  # lefty = y - 1if a[x][y] == 'G':b[i][j] = b[i][j] + 1x = iy = jwhile a[x][y] != '#':  # upx = x - 1if a[x][y] == 'G':b[i][j] = b[i][j] + 1if a[i][j+1] == '.':q.append((i, j+1))marking(a, i, j+1)if a[i+1][j] == '.':q.append((i+1, j))marking(a, i+1, j)if a[i][j-1] == '.':q.append((i, j-1))marking(a, i, j-1)if a[i-1][j] == '.':q.append((i-1, j))marking(a, i-1, j)mprint(a)mprint(b)def dfs(i, j):s.append((i, j))marking(a, i, j)while len(s):i, j = s.pop()x = iy = jwhile a[x][y] != '#':  # righty = y + 1if a[x][y] == 'G':b[i][j] = b[i][j] + 1x = iy = jwhile a[x][y] != '#':  # downx = x + 1if a[x][y] == 'G':b[i][j] = b[i][j] + 1x = iy = jwhile a[x][y] != '#':  # lefty = y - 1if a[x][y] == 'G':b[i][j] = b[i][j] + 1x = iy = jwhile a[x][y] != '#':  # upx = x - 1if a[x][y] == 'G':b[i][j] = b[i][j] + 1if a[i][j + 1] == '.':s.append((i, j + 1))marking(a, i, j + 1)if a[i + 1][j] == '.':s.append((i + 1, j))marking(a, i + 1, j)if a[i][j - 1] == '.':s.append((i, j - 1))marking(a, i, j - 1)if a[i - 1][j] == '.':s.append((i - 1, j))marking(a, i - 1, j)mprint(a)mprint(b)# bfs(3, 3)
dfs(3, 3)