기초 검색

제목은 간단하다. 바로 직사각형을 정하는 것이다. abcde는 열쇠로 각각 대문자에 대응한다. (이 대문자들은 문이다)
S에서 출발하여 G점에 도착할 수 있는지 없는지를 구하고 열쇠를 통해 문을 열어 G점에 도착한다
주의: 여기는 같은 알파벳(GS 제외)이 많을 수도 있고, 열쇠와 문이 없을 수도 있습니다.
자세히 검색:
자신이 원래 쓴 검색 오류는 위의 이러한 원인 때문에 귀속된 반환에 대해 좋은 방식, 즉 귀속 기반을 찾지 못해 후부 값을 분별하고 반환하기 어렵다
 
주의: 자신은 항상 잊어버린다. scanf는 끝에 남은 공백은 상관하지 않는다. 본 문제의 모든 줄의 끝에 공백이 있다.

#include<stdio.h>
#include<string.h>

struct pointer
{
    int x;
    int y;
}start;

int M,N;
char a[25][25];
int temp[110];
int tag[25][25];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void deal(char ch)
{
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
            if(a[i][j]==ch)
                a[i][j]='.';
    memset(tag,0,sizeof(tag));
}

int dfs(int x,int y)
{
    tag[x][y]=1;
    int tempx,tempy;
    for(int i=0;i<4;i++){
        tempx=dx[i]+x;
        tempy=dy[i]+y;
        if(tempx<0||tempy<0||tempx>=M||tempy>=N)
            continue;
        if(a[tempx][tempy]=='G')
            return 1;

        if(a[tempx][tempy]>='a'&&a[tempx][tempy]<='e'&&tag[tempx][tempy]==0){
            temp[a[tempx][tempy]]--;
            if(!temp[a[tempx][tempy]]){
                deal(a[tempx][tempy]-32);<span style="white-space:pre">		</span>// memset tag
                a[tempx][tempy]='.';
                if(dfs(start.x,start.y))
                    return 1;
            }
            else{
                a[tempx][tempy]='.';
                if(dfs(tempx,tempy))<span style="white-space:pre">			</span>// ， ， ， 
                    return 1;
            }
            continue;
        }

        if(a[tempx][tempy]=='.'&&tag[tempx][tempy]==0)
            if(dfs(tempx,tempy))
                return 1;
    }
    return 0;
}

int main()
{
    while(scanf("%d%d",&M,&N),M&&N)
    {
        memset(temp,0,sizeof(temp));
        memset(tag,0,sizeof(tag));

        for(int i=0;i<M;i++){
            scanf("%s",a[i]);<span style="white-space:pre">		</span>// ， 
            for(int j=0;j<N;j++){
                if(a[i][j]>='a'&&a[i][j]<='e')
                    temp[a[i][j]]++;

                if(a[i][j]=='S'){
                    start.x=i;
                    start.y=j;
                }
            }
        }

        if(dfs(start.x,start.y))
            puts("YES ");
        else
            puts("NO");
    }
    return 0;
}