首页 > 代码库 > NYOJ 迷宫寻宝（一）深搜

NYOJ 迷宫寻宝（一）深搜

2024-07-17 00:21:19   215人阅读

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=82

 

 

做这道题的时候迷迷糊糊的，，果然比较难。。最后也是没有做出来。。请教了一下学长，学长说我基础还不好。。基础果然重要，这道题是一道搜索题，我没有考虑钥匙在门后面的情况，比如aBbSAG 多亏学长指教，通过这道题对深搜的理解又加深了一步~

 

 #include <iostream>#include <cstdio> #include <cstring> using namespace std;int m,n;//行 列 char e[25][25];//储存地图 int a1,b1,c1,d1,e1;//这张图中对应门的钥匙的总数量  int startx,starty;//标记开始位置 int flag;//是否找到的标记 int book[21][21];int a2,b2,c2,d2,e2; //a2,b2,c2,d2,e2分别为可以找到的钥匙数量 int dfs(int x,int y){        if(e[x][y]==‘G‘)//找到     {        flag = 1;        return 1;    }    if(e[x][y]==‘X‘)//墙         return 0;    switch(e[x][y])    {        case ‘a‘:            a2++;            e[x][y] = ‘.‘;            break;        case ‘b‘:            b2++;            e[x][y] = ‘.‘;            break;        case ‘c‘:            c2++;            e[x][y] = ‘.‘;            break;        case ‘d‘:            d2++;            e[x][y] = ‘.‘;            break;        case ‘e‘:            e2++;            e[x][y] = ‘.‘;            break;        case ‘A‘:            if(a1 != a2)            {                return 0;            }    //        e[x][y] = ‘.‘;            break;        case ‘B‘:            if(b1 != b2)            {                return 0;            }            else    //        e[x][y] = ‘.‘;            break;        case ‘C‘:            if(c1 != c2)            {                return 0;            }    //        e[x][y] = ‘.‘;            break;        case ‘D‘:            if(d1 != d2)            {                return 0;            }    //        e[x][y] = ‘.‘;            break;        case ‘E‘:            if(e1 != e2)            {                return 0;            }    //        e[x][y] = ‘.‘;            break;        }                if(x+1<=m&&flag==0&&book[x+1][y]==0)    {            book[x+1][y] = 1;            dfs(x+1,y);            book[x+1][y] = 0;    }    if(y+1<=n&&flag==0&&book[x][y+1]==0)    {        book[x][y+1] = 1;        dfs(x,y+1);        book[x][y+1] = 0;    }    if(x-1>=1&&flag==0&&book[x-1][y]==0)    {        book[x-1][y] = 1;        dfs(x-1,y);        book[x-1][y] = 0;    }    if(y-1>=1&&flag==0&&book[x][y-1]==0)    {         book[x][y-1] = 1;        dfs(x,y-1);        book[x][y-1] = 0;    }     return 0;}int main(){        char temp;    //freopen("data.txt","r",stdin);    while(scanf("%d %d",&m,&n)&&(m+n)!=0)    {        memset(book,0,sizeof(book));        getchar();         a2 = 0;b2 =0;c2=0;d2=0;e2=0;        flag = 0;        a1=0;b1=0;c1=0;d1=0;e1=0;                for(int i=1;i<=m;i++)        {            for(int j=1;j<=n;j++)            {                while(scanf("%c",&temp)&&temp==‘ ‘);                e[i][j] = temp;                switch (e[i][j])                {                    case ‘a‘:                         a1++;                        break;                    case ‘b‘:                        b1++;                        break;                    case ‘c‘:                        c1++;                        break;                    case ‘d‘:                        d1++;                        break;                    case ‘e‘:                        e1++;                        break;                    case ‘S‘:                        startx = i;                        starty = j;                        break;                }            }            getchar();        }                dfs(startx,starty);                flag==1?cout<<"YES"<<endl:cout<<"NO"<<endl;    }            return 0;}

 


联系
我们