10. Codeup 묘지 에서 B - DFS 또는 BFS 를 널리 검색 합 니까?【2019.12.18】

#include
#include
#include
#include
#include
using namespace std;
int sx,sy,ex,ey;
char ma[8][8];//  
int dir[9][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},
{-1,-1},{1,-1},{-1,1},{0,0}};//    
struct node//BFS           
{
    int x,y;//    
    int step;
}s;
node now,nex;//  2   ，      
int judge(int x,int y)//    
{
    if(ma[x][y]=='S')
        return 0;
    if(x>7||x<0||y<0||y>7)
        return 0;
    return 1;
}
void change()//  
{
    for(int i=7;i>=0;i--)
        for(int j=7;j>=0;j--)
            if(ma[i][j]=='S')
            {
                ma[i][j]='.';
                if(i<=6)
                    ma[i+1][j]='S';
            }
}
void bfs(int c)
{
    int flag=0;//    
    queue<node>q;//BFS  
    s.x=sx,s.y=sy,s.step=0;
    q.push(s);//  
    int level=0;
    while(!q.empty())
    {
        now=q.front();//         
        if(now.step!=level)
        {
            change();
            level=now.step;
        }
        if(ma[now.x][now.y]=='S')//    
        {
            q.pop();
            continue;//      
        }
        if(now.step==8)//    ，    
        {
            flag=1;
            break;
        }
        q.pop();//      
        for(int i=0;i<9;i++)//  
        {
            if(judge(now.x+dir[i][0],now.y+dir[i][1])==1)
            {
                nex.x=now.x+dir[i][0];
                nex.y=now.y+dir[i][1];
                nex.step=now.step+1;
                q.push(nex);
            }
        }
    }
    if(flag==0)
        printf("Case #%d: No
",c);
    else
        printf("Case #%d: Yes
",c);
}
int main()
{
    int t,cnt=1;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0;i<8;i++)
            scanf("%s",ma[i]);
        for(int i=0;i<8;i++)
        {
            for(int j=0;j<8;j++)
            {
                if(ma[i][j]=='U')
                    sx=i,sy=j;
                if(ma[i][j]=='A')
                    ex=i,ey=j;
            }
        }
        bfs(cnt++);
    }
    return 0;
}