acm algorithm practice Jan 3 DFS

柔情只为你懂 2021-12-21 07:37 105阅读 0赞

poj 2488 knight's journey

**Background**  
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey  
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 \* 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

**Problem**  
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

\-------------------------------------------------

simple DFS problem, the key is "trace back"

pseudocode for DFS with traceback:

bool dfs(point p)

if (the count == total squares)

print and return true;

// 8 moving method

for each moving method

if the p' is white && not exceed the boundary

p'.color <----- grey

count ++

inqueue(p')

if (dfs(p') == true) // which means if the the bottom recursion return the true, no need to traceback

return true

p'.color <----white //trace back

count --

dequeue(p')

return false

more convient way is to use recursion times replace count, it is a traditional recursive problem.

bool dfs( int dip, int x, int y )
    {
     if( dip == n )
     {
        int j;
        for( j = 0; j<dip; j++ )//找到答案则输出路径
        {
         printf( "%c%d", path[j].y+'A', path[j].x+1 );
        }
        cout << endl;
        return true;
     }
     int i;
     for( i = 0; i<8; i++ )
     {
        int tx, ty;
        tx = x + a_x[i];
        ty = y + a_y[i];
        if( !isover(tx, ty) && !f[ty][tx] )
        {
         f[ty][tx] = true;
         path[dip].x = tx;
         path[dip].y = ty;
         if( dfs( dip+1, tx, ty ) )
          return true;
         f[ty][tx] = false;//算是回朔吧
        }
     }
     return false;
    }

here, since dip stands for the recursion times. and we use path\[\] record the path. it is not necessary to delete the value in path\[\] in traceback stage (the new data will overwrite the old error one)

转载于:https://www.cnblogs.com/ggppwx/archive/2011/01/05/1925974.html