halisi7

一个专注技术的组织

0%

炸弹人游戏—dfs

发表于 更新于 分类于 阅读次数： Valine：
炸弹人—dfs

问题描述

见（炸弹人游戏—bfs | halisi7）。

image-20220304164910720

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
char a[21][21];
int book[20][20] = { 0 };//初始值为0，表示没走过的路径
int n,m, max = 0, sum = 0 , mx, my ;
int getnum(int x, int y) {//
	int num = 0;//用来计数
	int tx, ty;
	//从四个方向统计可以消灭的敌人
	//向右
	tx = x; ty = y;

	while (a[tx][ty] != '#') {//判断是不是墙，不是墙继续
		if (a[tx][ty] == 'G') {
			num++;
		}
		ty++;
	}
	//向左
	tx = x; ty = y;
	while (a[tx][ty] != '#') {
		if (a[tx][ty] == 'G') {
			num++;
		}
		ty--;
	}
	//向上
	tx = x; ty = y;
	while (a[tx][ty] != '#') {
		if (a[tx][ty] == 'G') {
			num++;
		}
		tx++;
	}
	//向下
	tx = x; ty = y;
	while (a[tx][ty] != '#') {
		if (a[tx][ty] == 'G') {
			num++;
		}
		tx--;
	}
	return num;
}
void dfs(int x,int y) {
	int k,tx,ty;
	int next[4][2] = { {0,1},{0,-1},{1,0},{1,0} };//四个方向

	for (k = 0; k <= 3; k++) {
		tx = x + next[k][0];//下一个点的x坐标
		ty = y + next[k][1];//下一个点的y坐标
		if (tx<1 || tx>n || ty<1 || ty>m)//判断是否越界
			continue;
		if (book[tx][ty] == 0 && a[tx][ty] == '.') {//判断是否走过或是否为空地
			book[tx][ty] = 1;//没走过，是空地就标记
			sum = getnum(tx, ty);//统计这个点的消灭敌人数
			if (sum > max) {//如果消灭的敌人数比当前的最大值大就更新最大值，并记住该点
				max = sum;
				mx = tx;
				my = ty;
			}
			dfs(tx, ty);//继续下一个点

		}
		
	}
	return;//走不通了就返回上一步
}
int main() {
	int i, j, k, tail, head,  tx, ty,  startx, starty;
	
	
	printf("请输入你要输入几行几列的地图：");
	scanf_s("%d %d", &n, &m);
	printf("请输入的地图：\n");
	for (i = 0; i <= n - 1; i++)
		//for(j=1;j<=m;j++)
		scanf_s("%s", a[i], 20);//char用%s输入，scanf_s("%s",数组,数组大小)
	printf("请输入初始位置：");
	scanf_s("%d %d", &startx, &starty);//必须要初始位置
	book[startx][starty] = 1;
	max = getnum(startx, starty);//统计初始位置的炸弹消灭人数
	mx = startx;
	my = starty;
	dfs(startx, starty);
	printf("将炸弹放置到(%d，%d)处，可以消灭%d个敌人。", mx, my, max);
	getchar(); getchar();
	return 0;
}

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
请输入你要输入几行几列的地图：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#
#############
请输入初始位置：3 3

输出

1
将炸弹放置到(7，11)处，可以消灭10个敌人。
打赏一下作者~ ฅ( ̳• ◡ • ̳)ฅ