1.拯救小哈之BFS
具体题目描述 点击这里
参考代码
#include<iostream> #include<queue> using namespace std; struct node { int x; int y; int f; int s;//步数 }; int NEXT[4][2] = { {0,1},{1,0},{0,-1},{-1,0} }; int n, m, startx, starty, p, q, tx, ty, flag; queue<node> que; int main() { int a[51][51] = { 0 }, book[51][51] = { 0 }; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } cin >> startx >> starty >> p >> q; node nd; nd.x = startx; nd.y = starty; nd.f = 0; nd.s = 0; que.push(nd); book[startx][starty] = 1; flag = 0;//标记是否到达目标点 //当队列不为空的时候循环 while (!que.empty()) { //四个方向 node n1 = que.front(); for (int i = 0; i <= 3; i++) { tx = n1.x + NEXT[i][0]; ty = n1.y + NEXT[i][1]; //是否越界 if (tx < 1 || tx > n || ty <1 || ty > m) { continue; } if (a[tx][ty] == 0 && book[tx][ty] == 0) { book[tx][ty] = 1; node n2; n2.x = tx; n2.y = ty; n2.f = n1.f; n2.s = n1.s + 1; que.push(n2); } //如果到目标点了,停止扩展,结束循环 if (tx == p && ty == q) { flag = 1; break; } } if (flag) { break; } //当前点扩展结束,弹出改点. que.pop(); } if (que.size() > 0) { cout << que.back().s << endl; } return 0; }
2.炸弹人
游戏简述
通过放置炸弹的方法来消灭敌人，炸弹只能放置在空地上，炸弹可以向上下左右四个方向炸开，碰到敌人可以消灭，但是碰到墙则停止这个炸弹在这个方向上的威力。
现在有个特殊的关卡，只有一枚炸弹（炸弹威力大杀伤距离足够强威力足够大），请问这个炸弹放置在地图上的哪个空位上，能够消灭最多数量的敌人。
先将地图模型化，把墙用符号“#”表示，敌人用大写字母G表示，空地用英文点号“.”表示，整张地图可以抽象成一个二维数组。接下来我们使用BFS解决.
参考代码
#include<iostream> #include<queue> using namespace std; struct node { int x; int y;//横纵坐标 }; char a[25][25];//用来存储地图 int sum1, x, y,max1,mx,my,n,m,startx,starty,tx,ty; queue<node> que; int book[25][25];//定义一个标记 int NEXT[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };//方向数组 int getnum(int i, int j) { int sum; sum = 0;//用于计数 x = i; y = j; //向上统计 可以消灭的敌人 while (a[x][y] != '#') {//判断该点是不是墙 if (a[x][y] == 'G') { sum++; } x--; } //向下统计 x = i; y = j; while (a[x][y] != '#') { if (a[x][y] == 'G') { sum++; } x++; } //向左统计 x = i; y = j; while (a[x][y]!='#') { if (a[x][y] == 'G') { sum++; } y--; } //向右统计 x = i; y = j; while (a[x][y] != '#') { if (a[x][y] == 'G') { sum++; } y++; } return sum; } int main() { cin >> n >> m >> startx >> starty; for (int i = 0; i < n; i++) { cin >> a[i]; } //队列初始化 node nd; nd.x = startx; nd.y = starty; que.push(nd); max1 = getnum(startx, starty); mx = startx; my = starty; //队列不为空时进行循环 while (!que.empty()) { //枚举四个方向 node nd2 = que.front(); for (int i = 0; i <= 3; i++) { sum1 = 0; tx = nd2.x + NEXT[i][0]; ty = nd2.y + NEXT[i][1]; if (tx < 0 || tx > n - 1 || ty < 0 || ty > m - 1) {//判断是否越界 continue; } if (a[tx][ty] == '.' && book[tx][ty] == 0) { book[tx][ty] = 1; node nd3; nd3.x = tx; nd3.y = ty; que.push(nd3); sum1 = getnum(tx, ty); if (sum1 > max1) { max1 = sum1; mx = tx; my = ty; //cout << "哈哈哈" << max1 << endl; } } } que.pop(); } cout << "将炸弹放在:" << mx <<" "<< my << "处,最多可以消灭的敌人是" << max1 << endl; return 0; } /* 13 13 3 3 ############# #GG.GGG#GGG.# ###.#G#G#G#G# #.......#..G# #G#.###.#G#G# #GG.GGG.#.GG# #G#.#G#.#.#.# ##G...G.....# #G#.#G###.#G# #G#.#G#G#.#G# #GG.GGG#G.GG# #GG.GGG#G.GG# ############# */
运行结果
可以看出BFS的核心是:搜索所有的空白快,完毕后输出最小的即可.
该题也可使用DFS进行解决
参考代码2
#include<iostream> using namespace std; char a[25][25];//用来存储地图 int sum1, x, y, max1, mx, my, n, m, startx, starty, tx, ty; int book[25][25];//定义一个标记 int NEXT[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };//方向数组 int getnum(int i, int j) { int sum; sum = 0;//用于计数 x = i; y = j; //向上统计可以消灭的敌人 while (a[x][y] != '#') {//判断的点是不是墙 if (a[x][y] == 'G') { sum++; } x--; } //向下统计 x = i; y = j; while (a[x][y] != '#') { if (a[x][y] == 'G') { sum++; } x++; } //向左统计 x = i; y = j; while (a[x][y] != '#') { if (a[x][y] == 'G') { sum++; } y--; } //向右统计 x = i; y = j; while (a[x][y] != '#') { if (a[x][y] == 'G') { sum++; } y++; } return sum; } void dfs(int x, int y) { sum1 = getnum(x, y); if (sum1 > max1) { max1 = sum1; mx = x; my = y; } for (int i = 0; i <= 3; i++) { sum1 = 0; tx = x+ NEXT[i][0]; ty = y + NEXT[i][1]; if (tx < 0 || tx > n - 1 || ty < 0 || ty > m - 1) { continue; } //判断是否走过 if (a[tx][ty] == '.' && book[tx][ty] == 0) { book[tx][ty] = 1; dfs(tx, ty); } } return; } int main() { cin >> n >> m >> startx >> starty; for (int i = 0; i < n; i++) { cin >> a[i]; } book[startx][starty] = 1; max1 = getnum(startx, starty); mx = startx; my = starty; dfs(startx, starty); cout << "将炸弹放在:" << mx << " " << my << "处,最多可以消灭的敌人是" << max1 << endl; return 0; }
DFS解决的话,在于只要遍历过就行,无需回溯.
3.宝岛冒险
小哼通过秘密方法得到了一张不完整的钓鱼岛航拍地图。钓鱼岛由一个主岛和一些附属岛屿组成，小哼决定去钓鱼岛冒险。下面这个 10 * 10 的二维码矩阵就是钓鱼岛的航拍地图。图中数字代表海拔，0 表示海洋，1~9 表示陆地。小哼的飞机将会在（6，8）处，现在需要计算出小哼落地所在岛屿的面积（即有多少个格子）。
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
参考代码1–DFS
#include<iostream> using namespace std; int startx, starty,tx,ty,sum; int NEXT[4][2] = { {0,1},{1,0},{0,-1},{-1,0} }; int book[13][13], map[13][13],total= 1; //深搜 void dfs(int x, int y) { for (int i = 0; i < 4; i++) { tx = x + NEXT[i][0]; ty = y + NEXT[i][1]; //判断是否越界 if (tx < 1 || tx > 10 || ty < 1 || ty > 10) { continue; } //判断是否是陆地 if (map[tx][ty] >= 1 && map[tx][ty] <= 9 && !book[tx][ty]) { book[tx][ty] = 1; total++; dfs(tx, ty); } } } int main() { for (int i = 1; i <= 10; i++) { for (int j = 1; j <= 10; j++) { cin >> map[i][j]; } } book[6][8] = 1; dfs(6, 8); cout << total << endl; return 0; }
参考代码2—BFS
#include<iostream> #include<queue> using namespace std; struct node { int X; int Y; }; queue<node> que; int startx, starty,tx,ty,sum; int NEXT[4][2] = { {0,1},{1,0},{0,-1},{-1,0} }; int book[13][13], map[13][13],total= 1; void bfs(int x, int y) { node nd; nd.X = x; nd.Y = y; que.push(nd); while (!que.empty()) { node nd2; nd2 = que.front(); for (int i = 0; i <= 3; i++) { tx = nd2.X + NEXT[i][0]; ty = nd2.Y + NEXT[i][1]; //判断是否越界 if (tx < 1 || tx > 10 || ty < 1 || ty > 10) { continue; } if (map[tx][ty] >= 1 && map[tx][ty] <= 9 && !book[tx][ty]) { node nd3; nd3.X = tx; nd3.Y = ty; que.push(nd3); book[tx][ty] = 1; total++; } } que.pop(); } } int main() { for (int i = 1; i <= 10; i++) { for (int j = 1; j <= 10; j++) { cin >> map[i][j]; } } book[6][8] = 1; bfs(6, 8); cout << total << endl; return 0; } /* 1 2 1 0 0 0 0 0 2 3 3 0 2 0 1 2 1 0 1 2 4 0 1 0 1 2 3 2 0 1 3 2 0 0 0 1 2 4 0 0 0 0 0 0 0 0 1 5 3 0 0 1 2 1 0 1 5 4 3 0 0 1 2 3 1 3 6 2 1 0 0 0 3 4 8 9 7 5 0 0 0 0 0 3 7 8 6 0 1 2 0 0 0 0 0 0 0 0 1 0 38 */
