POJ 3083 Children of the Candy Corn DFS及BFS搜索

///这题不是很理解有待于重做，BFS+模拟，模拟有点麻烦  
#include<stdio.h>  
#include<string.h>  
#include<queue>  
using namespace std;  
queue<int> q;  
int w,h;  
char map[45][45];  
int dl[4][2]={{0,-1},{-1,0},{0,1},{1,0}};  
int vis[45][45];  
int dire,k;///指向当前移动方向。   
int left(int a,int b,int c,int d)  
{  
    if(a==c&&b==d)  
    return 0;  
    int t=(dire-1+4)%4;  
    if(map[a+dl[t][0]][b+dl[t][1]]!='#')  
    {  
        k++;  
        a=a+dl[t][0];b=b+dl[t][1];  
        dire=t;  
        left(a,b,c,d);  
    }  
    else  
    {  
        if(map[a+dl[dire][0]][b+dl[dire][1]]!='#')  
        {  
            k++;  
            a=a+dl[dire][0];  
            b=b+dl[dire][1];  
            left(a,b,c,d);  
        }  
        else  
        {  
            dire=(dire+1)%4;  
            if(map[a+dl[dire][0]][b+dl[dire][1]]!='#')  
            {  
                k++;  
                a=a+dl[dire][0];  
                b=b+dl[dire][1];  
                left(a,b,c,d);  
            }  
            else  
            {  
                dire=(dire+1)%4;  
                k++;  
                a=a+dl[dire][0];  
                b=b+dl[dire][1];  
                left(a,b,c,d);  
            }  
        }  
    }  
    return 0;  
}  
int right(int a,int b,int c,int d)  
{  
    if(a==c&&b==d)  
    return 0;  
    int t=(dire+1)%4;  
    if(map[a+dl[t][0]][b+dl[t][1]]!='#')  
    {  
        k++;  
        a=a+dl[t][0];b=b+dl[t][1];  
        dire=t;  
        right(a,b,c,d);  
    }  
    else  
    {  
        if(map[a+dl[dire][0]][b+dl[dire][1]]!='#')  
        {  
            k++;  
            a=a+dl[dire][0];  
            b=b+dl[dire][1];  
            right(a,b,c,d);  
        }  
        else  
        {  
            dire=(dire-1+4)%4;  
            if(map[a+dl[dire][0]][b+dl[dire][1]]!='#')  
            {  
                k++;  
                a=a+dl[dire][0];  
                b=b+dl[dire][1];  
                right(a,b,c,d);  
            }  
            else  
            {  
                dire=(dire-1+4)%4;  
                k++;  
                a=a+dl[dire][0];  
                b=b+dl[dire][1];  
                right(a,b,c,d);  
            }  
        }  
    }  
    return 0;  
}  
int bfs(int a,int b,int c,int d)  
{  
    memset(vis,0,sizeof(vis));  
    vis[a][b]=1;  
    q.push(a);q.push(b);  
    while(!q.empty())  
    {  
        int x,y,i;  
        x=q.front();q.pop();  
        y=q.front();q.pop();  
        for(i=0;i<4;i++)  
        {  
            int m,n;  
            m=x+dl[i][0];  
            n=y+dl[i][1];  
            if(m>=0&&m<h&&n>=0&&n<w&&map[m][n]!='#'&&vis[m][n]==0)  
            {  
                vis[m][n]=vis[x][y]+1;  
                if(m==c&&n==d)  
                {  
                    k=vis[m][n];  
                    return 0;  
                }  
                q.push(m);  
                q.push(n);  
            }  
        }  
    }  
    return 0;  
}  
int main()  
{  
    int cas;  
    scanf("%d",&cas);  
    while(cas--)  
    {  
        scanf("%d%d",&w,&h);  
        int i,s1,s2,e1,e2,j;  
        for(i=0;i<h;i++)  
        {  
            scanf("%s",map[i]);  
            for(j=0;j<w;j++)  
            {  
                if(map[i][j]=='S')  
                {  
                    s1=i;s2=j;  
                }  
                if(map[i][j]=='E')  
                {  
                    e1=i;e2=j;  
                }  
            }  
        }  
        k=1;  
        if(s1==0)  
        dire=3;  
        else if(s1==h-1)  
        dire=1;  
        else if(s2==0)  
        dire=2;  
        else  
        dire=0;  
        j=dire;  
        left(s1,s2,e1,e2);  
        printf("%d ",k);  
        dire=j;k=1;  
        right(s1,s2,e1,e2);  
        printf("%d ",k);  
        bfs(s1,s2,e1,e2);  
        printf("%d/n",k);  
        while(!q.empty())  
        q.pop();  
    }  
    return 0;  
}  

另http://jiyuede.blog.163.com/blog/static/33251921201022265225211/解答摘录如下：

1、至于求最短距离，毋庸置疑，肯定是bfs，这个就不多说了

2、对于向左和向右的理解上，我当初一直不明白，读了老长时间，没有看懂，到discuss里看了一个人的叙述，终于明白意思了……就是这样，一直沿着向左或向右的方向走，能走就走，不能走就回撤，所以这个dfs不能标记遍历过的点，这是很显然的。

3、dfs方向的选择，就是要保证沿着向左或者向右的方向走

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

struct T
{
    int row,col;
};
char chess[50][50];
int visited[50][50];
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int ldir1[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int ldir2[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int ldir3[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int ldir4[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
int rdir1[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
int rdir2[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int rdir3[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
int rdir4[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
queue<T> q;
int row,col;
int Min;
bool flag1;
bool flag2;
bool flag3;
int lstep;
int rstep;

void left(T,T);
void right(T,T);
void bfs();
bool check(int,int);
T ori,des;


int main()
{
    int i,j,k,m,n;

    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&col,&row);
            for(i=1;i<=row;i++)
            {
                getchar();
                for(j=1;j<=col;j++)
                {
                    scanf("%c",&chess[i][j]);
                    if(chess[i][j]=='S')
                    {
                        ori.row=i;
                        ori.col=j;
                    }
                    if(chess[i][j]=='E')
                    {
                        des.row=i;
                        des.col=j;
                    }
                }
            }
            memset(visited,0,sizeof(visited));
            while(!q.empty())
                q.pop();
            q.push(ori);
            Min=1;
            flag1=false;
            flag2=false;
            flag3=false;
            lstep=1;
            rstep=1;
            //寻找第一个可以走的点
            T sec;
            for(i=0;i<4;i++)
            {
                if(check(dir[i][0]+ori.row,dir[i][1]+ori.col))
                {
                    sec.row=dir[i][0]+ori.row;
                    sec.col=dir[i][1]+ori.col;
                    break;
                }
            }

            left(ori,sec);
            right(ori,sec);
            printf("%d %d ",lstep,rstep);
            bfs();
            printf("%d/n",Min);
    }
    return 0;
}

bool check(int x,int y)
{
    if(x>0&&x<=row&&y>0&&y<=col)
        if(chess[x][y]!='#')
            return true;
    return false;
}

void bfs()
{
    int i,j,k,m,n;
    T ch,lin;
    while(flag1==false)
    {
  k=q.size();
        for(j=0;j<k;j++)
  {
   ch=q.front();
    q.pop();
    for(i=0;i<4;i++)
    {
            if(check(ch.row+dir[i][0],ch.col+dir[i][1]))
            {
                lin.row=ch.row+dir[i][0];
                lin.col=ch.col+dir[i][1];
                q.push(lin);
                if(lin.row==des.row&&lin.col==des.col)
                {
                    flag1=true;
                    break;
                }
                chess[lin.row][lin.col]='#';
            }
     }
    if(flag1) break;
  }
        Min++;
    }
}
void left(T last,T cur)
{
    int x,y;
    int i;
    T next;
    if(flag2)    return;
    if(cur.row==des.row&&cur.col==des.col)
    {
        flag2=true;
        lstep++;
        return;
    }

    x=cur.row-last.row;
    y=cur.col-last.col;
    if(x==-1&&y==0)
       for(i=0;i<4;i++)
        {
            if(check(ldir1[i][0]+cur.row,ldir1[i][1]+cur.col))
            {
                lstep++;
                next.row=ldir1[i][0]+cur.row;
                next.col=ldir1[i][1]+cur.col;
                left(cur,next);
                if(flag2)   return;
            }
        }
    else
        if(x==0&&y==1)
        {
            for(i=0;i<4;i++)
            {
                if(check(ldir2[i][0]+cur.row,ldir2[i][1]+cur.col))
                {
                    lstep++;
                    next.row=ldir2[i][0]+cur.row;
                    next.col=ldir2[i][1]+cur.col;
                    left(cur,next);
                    if(flag2)   return;
                }
            }
        }
        else
            if(x==1&&y==0)
            {
                for(i=0;i<4;i++)
                {
                    if(check(ldir3[i][0]+cur.row,ldir3[i][1]+cur.col))
                    {
                        lstep++;
                        next.row=ldir3[i][0]+cur.row;
                        next.col=ldir3[i][1]+cur.col;
                        left(cur,next);
                        if(flag2)   return;
                    }
                }
            }
            else
            {
                for(i=0;i<4;i++)
                {
                    if(check(ldir4[i][0]+cur.row,ldir4[i][1]+cur.col))
                    {
                        lstep++;
                        next.row=ldir4[i][0]+cur.row;
                        next.col=ldir4[i][1]+cur.col;
                        left(cur,next);
                        if(flag2)   return;
                    }
                }
            }
}
void right(T last,T cur)
{
    int x,y,i;
    T next;
    if(flag3)    return;
    if(cur.row==des.row&&cur.col==des.col)
    {
        flag3=true;
        rstep++;
        return;
    }

    x=cur.row-last.row;
    y=cur.col-last.col;
    if(x==-1&&y==0)
       for(i=0;i<4;i++)
        {
            if(check(rdir1[i][0]+cur.row,rdir1[i][1]+cur.col))
            {
                rstep++;
                next.row=rdir1[i][0]+cur.row;
                next.col=rdir1[i][1]+cur.col;
                right(cur,next);
                if(flag3)   return;
            }
        }
    else
        if(x==0&&y==1)
        {
            for(i=0;i<4;i++)
            {
                if(check(rdir2[i][0]+cur.row,rdir2[i][1]+cur.col))
                {
                    rstep++;
                    next.row=rdir2[i][0]+cur.row;
                    next.col=rdir2[i][1]+cur.col;
                    right(cur,next);
                    if(flag3)   return;
                }
            }
        }
        else
            if(x==1&&y==0)
            {
                for(i=0;i<4;i++)
                {
                    if(check(rdir3[i][0]+cur.row,rdir3[i][1]+cur.col))
                    {
                        rstep++;
                        next.row=rdir3[i][0]+cur.row;
                        next.col=rdir3[i][1]+cur.col;
                        right(cur,next);
                        if(flag3)   return;
                    }
                }
            }
            else
            {
                for(i=0;i<4;i++)
                {
                    if(check(rdir4[i][0]+cur.row,rdir4[i][1]+cur.col))
                    {
                        rstep++;
                        next.row=rdir4[i][0]+cur.row;
                        next.col=rdir4[i][1]+cur.col;
                        right(cur,next);
                        if(flag3)   return;
                    }
                }
            }
}