Metal Steak

Hard to eat

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  0 Posts :: 79 Stories :: 0 Comments :: 0 Trackbacks

公告

aaaaaaaaaaaa

常用链接

留言簿(1)

我参与的团队

搜索

  •  

最新评论

#include <iostream>
using namespace std;

int searchf = 0, map[21][21], col, row, flag = 0;
const int drt[4][2= {{-10}, {0-1}, {01}, {10}};

struct struct_point
{
    
int row, col;
    struct_point()
    {
        row 
= col = -1;
    }
    
void set(int x, int y)
    {
        row 
= x;
        col 
= y;
    }
    
bool operator == (struct_point p)
    {
        
if((this->row == p.row)
         
&&(this->col == p.col))
            
return true;
        
return false;
    }
    
void clear()
    {
        row 
= col = -1;
    }
}pnt[
512], ans[512], source, target;

istream
& operator >> (istream& in, struct_point& p)
{
    
in >> p.row >> p.col;
    
return in;
}

ostream
& operator << (ostream& out, struct_point p)
{
    
out << "(" << p.row << "," << p.col << ")";
    
return out;
}

bool search(struct_point p);
void read();
void dfs(struct_point p, int ansf);

int main()
{
    read();

    pnt[
++searchf] = source;
    dfs(source, 
1);
    
if(!flag)
        cout 
<< -1 << endl;

    
return 0;
}

bool search(struct_point p)
{

    
for(int i = 1; i <= searchf; i++)
        
if(pnt[i] == p)
            
return true;
    
return false;
}

void read()
{
    memset(map, 
0sizeof map);

    cin 
>> row >> col;
    
for(int i = 1; i <= row; i++)
        
for(int j = 1; j <= col; j++)
            cin 
>> map[i][j];
    cin 
>> source >> target;
}

bool valid(struct_point p)
{
    
if(map[p.row][p.col] == 1)
        
return true;
    
return false;
}

void dfs(struct_point p, int ansf)
{
    
if(p == target)
    {
        flag 
= 1;
        cout 
<< source << "->";
        
for(int i = 1; i < ansf - 1; i++)
            cout 
<< ans[i] << "->";
        cout 
<< ans[ansf - 1<< endl;
    }
    
else
        
for(int i = 0; i <= 3; i++)
        {
            struct_point ptmp 
= p;
            ptmp.row 
+= drt[i][0];
            ptmp.col 
+= drt[i][1];
            
if(valid(ptmp) && !search(ptmp))
            {
                pnt[
++searchf] = ptmp;
                ans[ansf] 
= ptmp;
                dfs(ptmp, ansf 
+ 1);
                pnt[searchf
--= pnt[500]; //clear
            }
        }

}

posted on 2009-09-15 21:18 mad4alcohol 阅读(197) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理