python/C++课程/待整理知识/啊哈算法/bfs再解炸弹人.cpp

#include <iostream>
using namespace std;
struct node {
	int x;
	int y;
};
struct node que[401];
char map[50][50];
int visit[50][50];
int next_[4][2]= {{0,1},{1,0},{0,-1},{-1,0}};
int n,m,tx,ty,startx,starty,sum,max_=0;
int head,tail,mx,my;
int getboom(int x,int y) {
	int sum_=0,i,j;
	i=x,j=y;
	while(map[i][j]!='#') {
		if(map[i][j]=='G')
			sum_++;
		i--;
	}
	i=x;
	j=y;
	while(map[i][j]!='#') {
		if(map[i][j]=='G')
			sum_++;
		i++;
	}
	i=x;
	j=y;
	while(map[i][j]!='#') {
		if(map[i][j]=='G')
			sum_++;
		j--;
	}
	i=x;
	j=y;
	while(map[i][j]!='#') {
		if(map[i][j]=='G')
			sum_++;
		j++;
	}
	return sum_;

}
int main() {
	int i,j;
	n=13,m=13;
	startx=3,starty=3;
	for(i=1; i<=n; i++) {
		for(j=1; j<=m; j++) {
			cin>>map[i][j];
		}
	}
	head=tail=1;
	que[tail].x=startx;
	que[tail].y=starty;
	visit[startx][starty]=1;
	max_=getboom(startx,starty);
	tail++;
	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<1 || tx>n || ty<1 || ty>m)
				continue;
			if(map[tx][ty]=='.' && visit[tx][ty]==0) {
				visit[tx][ty]=1;
				que[tail].x=tx;
				que[tail].y=ty;
				tail++;
				sum=getboom(tx,ty);
				if(sum>max_) {
					max_=sum;
					mx=tx;
					my=ty;
				}
			}
		}
		head++;//四个方向都探索完了后，这个点就可以出队列了所以在for语句外写
	}
	cout<<max_<<' '<<mx<<' '<<my;
}
//#############
//#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#
//#############