再次大牛

再次求助大牛
杭电1010题。
http://acm.hdu.edu.cn/showproblem.php?pid=1010
大概意思是：给你一个迷宫，给你一个出口，和你当前的位置，要求你在T时间内出去。如果不能够出去就打印No。迷宫内有几种标识。
‘X’表示是石头，可以走，但是一旦走过这石头在下一秒就编程不可以走的。
‘S’你一开始的位置
‘D’出口的位置
‘.'不可以走的地方

求解决啊。

C/C++ code


#include <iostream>
#include <cmath>
using namespace std;

char maze[7][7];
bool bPath[7][7];
int N,M,T;
int ptStartX,ptStartY,ptDoorX,ptDoorY;
bool bFound;

int Recur(bool Path[7][7],int x,int y,int nLength)
{
    if (bFound==false && maze[x][y]=='D' && nLength==T)
    {
        bFound=true;
        cout<<"YES"<<endl;
        return 0;
    }
    else
        if (bFound)
        {
            return 0;
        }
    if (abs(x-ptDoorX)+abs(y-ptDoorY)>abs(T-nLength))
    {
        return -1;
    }
    if (bFound==false && x-1>=0 && Path[x-1][y]==false && maze[x-1][y]!='S' &&  maze[x-1][y]!='X')
    {
        Path[x-1][y]=true;
        Recur(Path,x-1,y,nLength+1);
        Path[x-1][y]=false;
    }
    if (bFound==false &&x+1<N && Path[x+1][y]==false && maze[x+1][y]!='S'&&  maze[x+1][y]!='X')
    {
        Path[x+1][y]=true;
        Recur(Path,x+1,y,nLength+1);
        Path[x+1][y]=false;
    }
    if (bFound==false &&y-1>=0 && Path[x][y-1]==false&& maze[x][y-1]!='S'&& maze[x][y-1]!='X')
    {
        Path[x][y-1]=true;
        Recur(Path,x,y-1,nLength+1);
        Path[x][y-1]=false;
    }
    if (bFound==false &&y+1<M && Path[x][y+1]==false &&maze[x][y+1]!='S'&& maze[x][y+1]!='X')
    {
        Path[x][y+1]=true;
        Recur(Path,x,y+1,nLength+1);
        Path[x][y+1]=false;
    }
}


int main(void)
{
    int i,j;    
    do 
    {
        bFound=false;
        cin>>N>>M>>T;
        if (N==0 && M==0 &&T==0)
        {
            break;
        }
    for (i=0;i<N;++i)
        for (j=0;j<M;++j)
        {
            cin>>maze[i][j];
            if (maze[i][j]=='S')
            {
                ptStartX=i;
                ptStartY=j;
            }
            else if (maze[i][j]=='D')
            {
                ptDoorX=i;
                ptDoorY=j;
            }
            bPath[i][j]=false;
        }
    
        Recur(bPath,ptStartX,ptStartY,0);
        if (bFound==false)
        {
            cout<<"NO"<<endl;
        }
    } while (1);
    return 0;
}

------解决方案--------------------
这道题杭电课件里有，，好像要用到什么奇偶剪枝。。
------解决方案--------------------

C/C++ code


#include <iostream>
#include <cmath>
using namespace std;

char maze[7][7];
int N,M,T;
int ptStartX,ptStartY,ptDoorX,ptDoorY;
bool bFound;

int Recur(int x,int y,int nLength)
{
    char tmp;
    if (bFound==false && maze[x][y]=='D' && nLength==T)
    {
        bFound=true;
        cout<<"YES"<<endl;
        return 0;
    }
    else if (bFound)
    {
        return 0;
    }
    if (nLength>T || ((T-nLength)-abs(x-ptDoorX)-abs(y-ptDoorY))%2!=0)
    {
        return -1;
    }

    tmp = maze[x][y];
    maze[x][y]='X';
    if (bFound==false && x-1>=0 && maze[x-1][y]!='S' &&  maze[x-1][y]!='X')
    {
        Recur(x-1,y,nLength+1);
    }
    if (bFound==false &&x+1<N && maze[x+1][y]!='S'&&  maze[x+1][y]!='X')
    {
        Recur(x+1,y,nLength+1);
    }
    if (bFound==false &&y-1>=0 && maze[x][y-1]!='S'&& maze[x][y-1]!='X')
    {
        Recur(x,y-1,nLength+1);
    }
    if (bFound==false &&y+1<M &&maze[x][y+1]!='S'&& maze[x][y+1]!='X')
    {
        Recur(x,y+1,nLength+1);
    }
    maze[x][y]=tmp;
}


int main(void)
{
    int i,j;    
    do 
    {
        bFound=false;
        cin>>N>>M>>T;
        if (N==0 && M==0 &&T==0)
        {
            break;
        }
        for (i=0;i<N;++i)
            for (j=0;j<M;++j)
            {
                cin>>maze[i][j];
                if (maze[i][j]=='S')
                {
                    ptStartX=i;
                    ptStartY=j;
                }
                else if (maze[i][j]=='D')
                {
                    ptDoorX=i;
                    ptDoorY=j;
                }
            }

            Recur(ptStartX,ptStartY,0);
            if (bFound==false)
            {
                cout<<"NO"<<endl;
            }
    } while (1);
    return 0;
}

相关推荐