第一题：
解题大致过程：
首先要提前准备的四个数组
1.1 第一个是用来存放地图的
1.2 第二个用来存放保存记录，
1.3 第三个用来进行队列的
1.4 第四个是存放上下左右方向的
就一个队列循环结束即可，不需要像深搜一样
在while 队列中
3.1 队列过程中每到一个位置时会进行上下左右进行列举，这里用一个for循环，
3.2 在循环中开始获取下一个位置，获取到之后首先判断是否当前位置是超过这张地图的范围，是的话 continue 直接换位置
3.3 判断这个点是否为障碍物，或者是否曾经访问过这个点，不是的话增加到队列中尾部加一
3.4 判断这个点是否是终点，是的话用一个flag=1来表示已经找到了，直接退出for循环列举方向
3.5 结束for在while中判断是否得到flag为1的信号及时退出，没有的话说明这个点已经所有位置都访问过，进行队列中下一个位置
输入条件：
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
1 1 4 3
代码：
#include <stdio.h> struct node{ int x; //横坐标 int y; //纵坐标 int f; //父亲在队列中的编号 int s; //步数 }; int main() { struct node que[2501]; //因为地图不会超过50*50的，也因此队列扩展不会超过2500个 int a[51][51]={0},book[51][51]={0}; int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; int head,tail,n,m,i,j,startx,starty,p,q,flag,tx,ty,k; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]); scanf("%d%d%d%d",&startx,&starty,&p,&q); //进行队列初始化 head = 1; tail = 1; //往队列中插入迷宫入口坐标 que[tail].x = startx; que[tail].y = starty; que[tail].f = 0; que[tail].s = 0; tail++; book[startx][starty]=1; flag = 0; // 用来标记是否达到目标点，0表示暂时还没有到达 //当队列不为空的时候循环 while(head<tail) { for(k=0;k<=3;k++) { //计算下一个点的坐标 tx = que[head].x+next[k][0]; ty = que[head].y+next[k][1]; //判断是否越界 if(tx<1||tx>n||ty<1||ty>m){ continue; } //判断是否是障碍物或者已经在路径中 if(a[tx][ty]==0&&book[tx][ty]==0) { //把这个点标记为已经走过 //注意宽搜每个点只入队一次，所以和深搜不同，不需要将book还原 book[tx][ty]=1; //插入新的点到队列中 que[tail].x = tx; que[tail].y = ty; que[tail].f = head; que[tail].s = que[head].s+1; tail++; } //判断到目标点了，停止扩展，任务结束，退出循环 if(tx==p&&ty==q) { flag=1; break; } } if(flag==1) break; head++; //第一个扩展点结束后才进行增1 } //指向末尾最后一个的点数 printf("%d",que[tail-1].s); return 0; }
运行结果为：7
——————————————————————————————————————
第二题 找到合理的位置求出能够消灭最多的敌人
必须在空旷的位置走
输入条件：
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#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############
代码：
#include <stdio.h> struct node{ int x; //横坐标 int y; //纵坐标 }; char a[20][21]; //定义地图 //得到对应的点能炸敌人的和 int getnum(int i,int j) { int sum,x,y; 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() { struct node que[401]; int head,tail; //定义头尾 int book[20][20]={0}; int next[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; int i,j,n,m,startx,starty,mx,my,tx,ty,sum=0,max; scanf("%d%d%d%d",&n,&m,&startx,&starty); //输入行列 for(i=0;i<n;i++) scanf("%s",a[i]); //队列初始化 head=1; tail=1; //往队列中插入小人的起始坐标 que[tail].x = startx; que[tail].y = starty; tail++; book[startx][starty]=1; max = getnum(startx,starty); mx = startx; my = starty; //当队列不为空的时候循环 while(head<tail) { //枚举四个方向 for(i=0;i<4;i++) { //尝试走的下一个点坐标 tx=que[head].x+next[i][0]; ty=que[head].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; //插入新的扩展点到队列中 que[tail].x = tx; que[tail].y = ty; tail++; //统计当前消灭敌人总数 sum = getnum(tx,ty); if(sum>max){ max = sum; mx = tx; //记录点 my = ty; }//if }//if }//for head++; //进行扩展 }//while printf("炸弹放在(%d,%d)中消灭最多敌人数：%d",mx,my,max); return 0; }
输出结果为：炸弹放在(7,11)中消灭最多敌人数：10
