There is a will there is a way!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  4 随笔 :: 0 文章 :: 29 评论 :: 0 Trackbacks

这里的迷宫是由0 1表示的 0表示墙, 1表示能通过

这里我用了const int row=7,column=13;你当然可以改动这个参数. 运行后回把其中的一条路径改成其它数字
你会看到的,

#include  < iostream >
#include 
< stack >
using   namespace  std;
const   int  row  =   7 ;
const   int  column  =   13 ;
int  table[row][column];
// struct position{
  
//   int prow;
    
// int pcolumn;
// };
void  settable()
{
    
    cout
<< " Please input table[ " ;
    cout
<< row << " ][ " ;
    cout
<< column;
    cout
<< " ](using 0 or 1):\n " ;
    
for ( int  i = 0 ;i < row;i ++
        
for ( int  j = 0 ;j < column;j ++ )
            cin
>> table[i][j];
    
// cout<<"Input 1 go on and 0 end:\n";
    
}

int  solvepass(stack < int >   & P, int  i, int  j)
{
    
int  count = 0 ;
   
//  int count1=0;
     while (i != row - 1   ||  j != column - 1 )
    
{
        count
= 0 ;
       
//  count1=0;
         if (i - 1 >= 0   &&  table[i - 1 ][j] == 1
        
{
            count
= 1 ;
            table[i][j]
= 9 ;
            P.push(i);P.push(j); 
//  cout<<"i="<<i<<" j="<<j<<endl;
            i -= 1 // cout<<"i="<<i<<" j="<<j<<endl;
             continue ;
        }

        
if (i + 1 < row  &&  table[i + 1 ][j] == 1 )
        
{
            count
= 1 ;
            table[i][j]
= 9 ;
            P.push(i);P.push(j);
// cout<<"i="<<i<<" j="<<j<<endl;
            i += 1 ; // cout<<"i="<<i<<" j="<<j<<endl;
              continue ;
        }
 
        
if (j - 1 >= 0   &&  table[i][j - 1 ] == 1 )
        
{
            count
= 1 ;
            table[i][j]
= 9 ;
            P.push(i);P.push(j);
// cout<<"i="<<i<<" j="<<j<<endl;
            j -= 1 // cout<<"i="<<i<<" j="<<j<<endl;
             continue ;
        }

        
if (j + 1 < column  &&  table[i][j + 1 ] == 1 )
        
{
            count
= 1 ;
            table[i][j]
= 9 ;
            P.push(i);P.push(j);
// cout<<"i="<<i<<" j="<<j<<endl;
            j += 1 ; //  cout<<"i="<<i<<" j="<<j<<endl;
             continue ;
        }

        
if (count == 0 )
        
{
            
int  n = P.top();
            P.pop();
            
int  m = P.top();
            P.pop();
            table[i][j]
= 2 ; // cout<<"i="<<i<<" j="<<j<<endl;
            i = m;j = n; // cout<<"i="<<i<<" j="<<j<<endl;
        }

       
//  else return 1;
       
//  count1=1;
    }

     
     P.push(row
- 1 );P.push(column - 1 ) ;
      table[row
- 1 ][column - 1 ] = 9 ;
}

void  outputtable()
{
    
// cout<<"Result table is:\n";
     for ( int  i = 0 ;i < row;i ++ )
    
{
        cout
<< endl;
        
for ( int  j = 0 ;j < column;j ++ )
            cout
<< table[i][j] << "   " ;
        }

}

void  outputpass(stack < int >& P)
{
    stack
< int >  S;
    cout
<< " \nThe result pass is:\n " ;
    
while ( ! P.empty())
    
{
        
int  sp = P.top();
        P.pop(); 
        
int  q = P.top();  P.pop();
        S.push(q); S.push(sp);
        
    }

    
while ( ! S.empty())
    
{
        
int  j = S.top();
        S.pop();
        
int  i = S.top();
        S.pop();
        cout
<< " ( " << i << " , " << j << " ) \n " ;
    }

}

int  main()
{
    
// int row,column;
    
// int table[row][column];
    stack < int >  P; // save the pass ways
     int  s;
    cout
<< " Input 1 go on and 0 end:\n " ;
    
while (cin >> s)
    
{
        
if ( ! s)  break ;
        settable(); 
// set table
        cout << " \nThe orenage table is:\n " ;
        outputtable();
        solvepass(P,
0 , 0 );  // solve this problem
        cout << " \nThe result table is:\n " ;
        outputtable();
        outputpass(P);
        cout
<< " Input 1 go on and 0 end:\n " ;
    }

    
return   1 ;
}

posted on 2006-04-10 23:21 王直元 阅读(608) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理