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

Re:各位大大,小弟求一个c的dfs代码

Posted by jiangjin at 2015-08-07 09:20:00 on Problem 3984
In Reply To:各位大大,小弟求一个c的dfs代码 Posted by:panshenjia at 2012-07-18 14:31:40
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std ;
struct point {
    int row ;
    int col ;
    int fa;
}po[30];
struct next{
    int row ;
    int col ;
};
int times;
int mapp[6][6] ;
int step[4][2] = {{0,1} , {1,0} ,{0,-1} , {-1,0} } ;
void dfs(int par) {
    if( par ) dfs(po[par].fa) ;
    if( par > 0 ) {
        printf("(%d, %d)\n",po[par].row,po[par].col) ;
    }
    return ;
}
void bfs(){
queue<next> Q ;
    po[1].fa = 0 ;
    po[1].row = 0 ;
    po[1].col = 0 ;
    times = 1 ;
    int flag  ;
    int num = 1 ;
    while(!Q.empty() ) {
        Q.pop() ;
    }
    next st ;
    st.row = 0 ;
    st.col = 0 ;
    Q.push(st) ;
    while(!Q.empty() ) {
        st = Q.front() ;
        Q.pop() ;
        for( int i = 0 ; i < 4 ; ++i ) {
            next temp ;
            temp.row = st.row + step[i][0] ;
            temp.col = st.col + step[i][1] ;
            if( temp.row>=0 && temp.row < 5&& temp.col >=0 && temp.col < 5 && !mapp[temp.row][temp.col]) {
                Q.push(temp) ;
                mapp[temp.row][temp.col] = true ;
                po[++num].fa = times;
                po[num].row = temp.row ;
                po[num].col = temp.col ;
                if( temp.row == 4 && temp.col == 4) {
                        flag = num ;
                    break ;
                }
            }
        }
        times++ ;
    }
    dfs(flag) ;
    return ;
}
int main () {
    for( int i = 0 ;  i < 5 ; ++i ) {
        for(int j = 0 ; j < 5 ; ++j ) {
            scanf("%d",&mapp[i][j] ) ;
        }
    }
    bfs( ) ;
}










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