| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:各位大大,小弟求一个c的dfs代码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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator