爆弾人の広さ優先—C
5746 ワード
二次元地図では、どの点が最も多くの敵を爆破できるかを探し出し、広さを用いて各到達点を優先的に遍歴し、各点が爆破できる敵の数を計算し、最も多くの点を探し出す.
#include
char a[20][20];//
struct node
{
int x;
int y;
};
int getnum(int x,int y)
{
int sum=0 ,i,j;
i=x;
j=y;
while(a[i][j]!='#')
{
if(a[i][j]=='G')
sum++;
j++;
}
i=x;
j=y;
while(a[i][j]!='#')
{
if(a[i][j]=='G')
sum++;
i++;
}
i=x;
j=y;
while(a[i][j]!='#')
{
if(a[i][j]=='G')
sum++;
j--;
}
i=x;
j=y;
while(a[i][j]!='#')
{
if(a[i][j]=='G')
sum++;
i--;
}
return sum;
}
int main()
{
int i,j,k,startx,starty,tx,ty;
int n,m,max,sum,mx,my;
int book[20][20]={0};
struct node queue[400],t;
int head,tail;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
scanf("%d%d%d%d",&n,&m,&startx,&starty);
for(i=0;i<=n-1;i++)
scanf("%s",a[i]);// n
head=1;
tail=1;
queue[tail].x=startx;
queue[tail].y=starty;
tail++;
book[startx][starty]=1;
max=getnum(startx,starty);
while(headfor(k=0;k<=3;k++)
{
tx=t.x+next[k][0];
ty=t.y+next[k][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;
queue[tail].x=tx;
queue[tail].y=ty;
tail++;
sum=getnum(tx,ty);
if(sum>max)
{
max=sum;
mx=tx;
my=ty;
}
}
}
head++;
}
printf(" (%d,%d) , %d",mx,my,sum);
return 0;
}