poj 3083 Children of the Candy Corn （深搜+广搜）

题意：计算从S到E走得步数，分别按向左优先，向右优先，最短路径来计算

memory  476k  time 79MS  Code Length  3898B

速度比较慢。这是我第一次用深搜跟广搜，花了好几天才做出来，真菜。

分析： 向左优先跟向右优先都要用深搜， 最短路径用广搜，因为前两者走过去就一直走下去，直到无路可走再回过去找另外的路。而后者的路径类似树的按层遍历，先找各个方向，再在每个方向找各个方向。

 

 

#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
using namespace std;

int w, h;
char maze[50][50];

int leftx[4] = {-1, 0, 1, 0}; 
int lefty[4] = {0, -1, 0, 1};

int rightx[4] = {1, 0, -1, 0};
int righty[4] = {0, -1, 0, 1};

int flag[50][50];
int cou = 1;

//往左

int isok1(int i, int xs, int ys)
{
    if(maze[ys+lefty[i]][xs+leftx[i]] == '.' || maze[ys+lefty[i]][xs+leftx[i]] == 'E')
        return 1;
    else return 0;
}

int a;
void dfsleft(int i, int xs, int ys, int xe, int ye)
{
    
    int j, k;
    stack <int> st;   

    for(j=0; j<4&&!a ; i++, j++)  
    {
        if(i == 4)
            i = 0;
        if(ys+lefty[i] >=0 && ys+lefty[i] < h && xs+leftx[i]>=0 && xs+leftx[i] < w)
        {
            if(isok1(i, xs, ys))
            {
                xs += leftx[i];
                ys += lefty[i];
                cou++;
                if(maze[ys][xs] == 'E'&&!a)
                {
                    printf("%d ", cou);
                    a = 1;
                    return;
                }
    //            printf("(%d,%d)", ys, xs);

                flag[ys][xs] = 1;
                st.push(i);
                if(i == 0)
                    i = 3;
                else if(i == 2)
                    i = 1;
                else if(i == 3)
                    i = 2;
                else if(i == 1)
                    i = 0;
                
                dfsleft(i, xs, ys, xe, ye);
                k = st.top();
                st.pop();
                if(k == 3)
                    i = 1;
                else if(k == 1)
                    i = 3;
                else if(k == 2)
                    i = 0;
                else if(k == 0)
                    i = 2;
                
                xs += leftx[i];
                ys += lefty[i];
                cou++;
            }
        }
    }
}

//往右

int isok2(int i, int xs, int ys)
{
    if(maze[ys+righty[i]][xs+rightx[i]] == '.' || maze[ys+righty[i]][xs+rightx[i]] == 'E')
        return 1;
    
    else
        return 0;
}

void dfsright(int i, int xs, int ys, int xe, int ye)
{
    int j;
    if(xs == xe && ys == ye&&!a)
    {
        printf("%d ", cou);
        a = 1;
        return;
    }
    
    for(j=0; j<4&&!a; i++, j++)
    {
        if(i == 4)
            i = 0;
        if(ys+righty[i] >=0 && ys+righty[i] < h && xs+rightx[i]>=0 && xs+rightx[i] <w)
        {
            if(isok2(i, xs, ys))
            {
                xs += rightx[i];
                ys += righty[i];
                cou++;
                flag[ys][xs] = 1;
                if(i == 0)
                    i = 3;
                else if(i == 1)
                    i = 0;
                else if(i == 2)
                    i = 1;
                else if( i == 3 )
                    i = 2;

                dfsright(i, xs, ys, xe, ye);

                if(i == 3)
                    i = 0;
                else if(i == 0)
                    i = 1;
                else if(i == 1)
                    i = 2;
                else if( i == 2 )
                    i = 3;
                xs -= rightx[i];
                ys -= righty[i];
                cou++;
            }
        }
    }
}

void bfs(int xs, int ys, int xe, int ye)
{
    int i=0, xxs, yys;
    int step[50][50];
    queue<int> qx, qy;
    
    memset(step, 0, sizeof(step));
    step[ys][xs] = 1;
    qx.push(xs);
    qy.push(ys);
    while(!qx.empty())
    {
        xs = qx.front();
        ys = qy.front();
        qx.pop();
        qy.pop();
        xxs = xs;
        yys = ys;
        for(i=0; i<4; i++)
        {
            xs = xxs;
            ys = yys;
            if(ys+righty[i] >=0 && ys+righty[i] < h && xs+rightx[i]>=0 && xs+rightx[i] <w)
            {
                if(isok2( i, xs, ys) && !flag[ys+righty[i]][xs+rightx[i]])
                {
                    step[ys+righty[i]][xs+rightx[i]] = step[ys][xs] + 1;
                    
                    xs += rightx[i];
                    ys += righty[i];
                    
                    flag[ys][xs] = 1;
            //        printf("(%d, %d)", ys, xs);

                    qx.push(xs);
                    qy.push(ys);    
                    
                    if(xs == xe && ys == ye)
                        break;
                }
            }
        }
    }
    printf("%d\n", step[ye][xe]);
}

int main()
{
    int n, i, j, xs, ys, xe, ye, k=0;
     
    freopen("3083.dat", "r", stdin);
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d%d", &w, &h);
        memset(maze, 0, sizeof(maze));
        for(j=0; j<h; j++)
        {
            scanf("%s", maze[j]);
            for(i=0; i<w; i++)
            {
                if(maze[j][i] == 'S')
                {
                    xs = i;
                    ys = j;
                }
                if(maze[j][i] == 'E')
                {
                    xe = i;
                    ye = j;
                }
            }        
        }        
        a = 0;
        cou = 1;
        dfsleft(k, xs, ys, xe, ye);//left     
        cou = 1;
        a = 0;
        dfsright(0, xs, ys, xe, ye); //right        
        memset(flag, 0, sizeof(flag)); //shortest road

        flag[ys][xs] = 1;        
        bfs(xs, ys, xe, ye);
    }
    return 0;
}