Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

dfs + bfs 关键还是 方向的确定 一次过 看我代码

Posted by Smile_7 at 2013-03-23 14:08:22 on Problem 3083
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#define  MAX 50

using namespace std;

struct point
{
    int  x , y;
    int step;
};

int visit[MAX][MAX];
char maze[MAX][MAX];
int  mov_left[4][2] = {{0,-1},{1,0},{0,1},{-1,0}} ; // 靠左走
int  mov_righ[4][2] = {{0,1},{1,0},{0,-1},{-1,0}} ; // 靠右走
int d1 , d2 ;
int start[2];
int finish[2];
int  w , h ;

int dfs(int x,int y,int d,int move[][2])
{
    int step ,temp , tx , ty ;
    if(x == finish[0] && y == finish[1])
        return 1 ;
    for(int i = 0; i < 4 ; i++)
    {
        temp = (d + i) % 4 ;
        tx   =  x + move[temp][1] ;
        ty   =  y + move[temp][0] ;
        if(tx>=0 && tx<h && ty>=0 && ty<w && !visit[tx][ty])
            break ;
    }
    step = dfs(tx,ty,(temp + 3)%4,move) + 1;
    return step;
}

int bfs()
{
    memset(visit,0,sizeof(visit));
    queue<point> Q;
    point p;
    p.x = start[0] ;
    p.y = start[1] ;
    p.step = 1;
    visit[p.x][p.y] = 1 ;
    Q.push(p);

    while(!Q.empty())
    {
        p = Q.front();
        Q.pop();
        if(p.x == finish[0] && p.y == finish[1])
            return p.step ;
        for(int i = 0 ; i < 4 ; i ++)
        {
            point temp ;
            temp.x = p.x + mov_left[i][1] ;
            temp.y = p.y + mov_left[i][0] ;
            if(temp.x>=0 && temp.x<h && temp.y>=0 && temp.y<w && maze[temp.x][temp.y]!='#' && !visit[temp.x][temp.y])
            {
                visit[temp.x][temp.y] = 1;
                temp.step = p.step + 1 ;
                Q.push(temp) ;
            }
        }
    }
    return 0;
}


int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    cin>>n;
    while(n--)
    {
        int i , j ;
        cin>>w>>h;
        memset(visit,0,sizeof(visit));

        for(i = 0; i < h; i++)
        {
            for(j = 0; j < w; j++)
            {
                cin>>maze[i][j];
                if(maze[i][j] == '#')
                {
                    visit[i][j] = 1;
                }
                if(maze[i][j] == 'S')
                {
                    start[0] = i ;
                    start[1] = j ;
                }
                if(maze[i][j] == 'E')
                {
                    finish[0] = i ;
                    finish[1] = j ;
                }
            }
        }
        if(start[0] == 0)
        {
            d1 = 1 ;
            d2 = 1 ;
        }
        else if(start[0] == h-1)
        {
            d1 = 3 ;
            d2 = 3 ;
        }
        else if(start[0] == w-1)
        {
            d1 = 2 ;
            d2 = 0 ;
        }
        else
        {
            d1 = 0 ;
            d2 = 2 ;
        }
        cout<<dfs(start[0],start[1],d1,mov_left)<<" ";
        cout<<dfs(start[0],start[1],d2,mov_righ)<<" ";
        cout<<bfs()<<endl;
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator