团战可以输、提莫必须死
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
为了一些你们不知道的原因,我们把LOL的地图抽象为一个n×m的矩阵
提莫积攒了k个蘑菇准备种到地图上去，因为提莫的背篓漏了，所以每一个提莫走过的地方都会被摆下一个蘑菇，两个蘑菇同时种在一个地方的话就会爆炸，所以一旦即将出现这种情况，提莫会直接传送回家，防止自己被炸死
之前的排位赛中因为乱种蘑菇提莫已经被骂了好多次了，所以这次提莫特地查资料对当前地图的各个位置种下蘑菇的价值做了统计，但是因为提莫行动比较笨拙，所以他每次只能移动到上下左右四个方向的格子中（如果该方向有格子的话
每次行走提莫会从四个方向挑选一个权值最大的方向，如果有最大的权值有多个，他会从这多个相同的最大权值之中找出没有走过并且按照上下左右的优先顺序挑选一个合适的方向走。如果最大权值都被走过了，他会心灰意冷的传送回家，此时直接输出”BOOM”
（提莫会顺手在他的起点顺手种一个蘑菇下去
Input
多组输入。
输入第一行包含地图大小n，m，蘑菇数量k。（1 <= n,m <= 100,1 <= k <= n*m)
接下来的n行每行有m个数（并且保证每个数的范围[1,1e5)
接下来两个整数x,y代表提莫的起点
Output
如果走到最后没有地方可以种蘑菇了，但蘑菇还没全部种完，输出”BOOM”.
如果蘑菇在半途中种完了，输出提莫所处的坐标”Teemo: x y”.
Sample Input
3 3 3
1 2 3
4 5 6
7 8 9
2 2
3 3 5
1 2 3
4 5 6
7 8 9
2 2
Sample Output
Teemo: 3 3
BOOM
Hint
Source
2015级《程序设计基础II》计科软件通信期末上机考试2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
using namespace std;
int ma[121][121];// 用来表示n*m矩阵
int v[121][121]; // 标记数组，看是否走过，因为重复会BOOM; 都要先清零。
int n,m,k;
struct node
{
int x, y, ans; // 行标，列标，蘑菇数
}que[232], p, q; // que【】数组 先存进而方便更新p 所在格子的位置情况；（p，q，类似于链表中的指针操作）
int xy[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};// 题目要求按照上下左右顺序来挑选相同的最大权值；方便max 的取值；
void bfs(int a, int b)
{
int front = 0, rear = 0;
p.x = a;
p.y = b;
p.ans = 1; // 初始化， 提莫的起点坐标，并丢下一个蘑菇
que[rear++] = p; // 存放p
v[p.x][p.y] = 1; // 已经走过
while(front < rear)
{
q = que[front++]; // 以q为节点中心判断四个方向的最大值及当前蘑菇情况；
int max = 0, flag = 0; // flag 用来标记 有最大值但不能继续重复走 以及 没地可走但剩下蘑菇的情况；
if(q.ans >= k)
{
cout<<"Teemo: "<<q.x<<" "<<q.y<<endl;
return ; // 返回空，跳出循环；
}
for( int i = 0; i <= 3; i++)
{
if(ma[q.x + xy[i][0]][q.y + xy[i][1]] > max)
max = ma[q.x + xy[i][0]][q.y + xy[i][1]]; // 求最大权值
}
for(int i = 0; i <= 3; i++)
{
p.x = q.x + xy[i][0];
p.y = q.y + xy[i][1];
if(p.x > 0 && p.x <= n && p.y > 0 && p.y <= m && v[p.x][p.y] == 0 && ma[p.x][p.y] == max)
// 尝试四个方向 当 1.未超出边界 2. 未重复走 3.当前方向是最大权值方向 时 为可行
{
p.ans = q.ans + 1;
v[p.x][p.y] = 1;
que[rear++] = p;
flag = 1;
}
}
if(flag == 0)
{
cout<<"BOOM"<<endl;
return ;
}
}
}
int main()
{
int a,b;
while(cin>>n>>m>>k)
{
memset(v,0,sizeof(v));
memset(ma,0,sizeof(ma));
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin>>ma[i][j];
}
}
cin>>a>>b;
bfs(a , b);
}
return 0;
}转载自原文链接, 如需删除请联系管理员。
原文链接：BFS团战可以输、提莫必须死（转载），转载请注明来源！