Chinaunix首页 | 论坛 | 博客

没有代码的日子会死djkpengjun.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

djkpengjun

  • 博客访问： 1517493
  • 博文数量： 399
  • 博客积分： 8508
  • 博客等级： 中将
  • 技术积分： 5302
  • 用 户 组： 普通用户
  • 注册时间： 2009-10-14 09:28
个人简介

能力强的人善于解决问题，有智慧的人善于绕过问题。 区别很微妙，小心谨慎做后者。

文章分类

全部博文（399）

文章存档

2018年（3）

2017年（1）

2016年（1）

2015年（69）

2013年（14）

2012年（17）

2011年（12）

2010年（189）

2009年（93）

我的朋友
最近访客
推荐博文
相关博文
数学家旅游

分类： LINUX

2009-12-11 14:12:13

Description

有一个城市的道路由规则的方砖组成。有一位数学家来参观，他可沿方砖的边沿行走，有四种方法：n(0,1)，s(0,-1)，e(1,0)，w(-1,0)，但他是一个很怪的数学家，他会走一段时间休息一会儿，然后继续走。他有几个很特别的特性：
（1）不喜欢休息后走的方向和休息前的一样；
（2）第一次休息前走一步，休息后走的距离比休息前走的距离长一步；
（3）不喜欢重复走同一个地方；
（4）要走回出发点。
我们称他的路线是一个golygon。我们可以将出发的地点标记为(0,0)，城市有几个地点正在施工，是不可以通行的。为了这位奇怪的科学家可以旅游得开心，我们决定帮他设计旅游的方案，找出城市中有多少个他希望的golygon。

Input

输入数据的第一行是golygons最大边的大小（不大于20），第二行是施工地点的个数（不大于50），以下的每一行有两个数字，表示施工的地点的坐标。

Output

输出每一个golygon的走法，每个占一行，最后输出golygon的个数。形式如输出样例。

Sample Input 

8
2
-2 0
6 -2

Sample Output 

wsenenws
Found 1 golygon(s).

Source

#include
#include
#include
#include
using namespace std;
int x[]={0,0,1,-1};
int y[]={1,-1,0,0};
int visited[21][21];

class move
{
public:
    int dx,dy;
    move(int x,int y)
    {
        dx=x;dy=y;
    }
    bool operator<(const move t) const
    {
        if(t.dx>dx && t.dy>dy)
        return true;
    }
    bool operator==(const move t)const
    {
        if(t.dx==dx && t.dy==dy)
            return true;
        return false;
    }
    bool operator!=(const move t)const
    {
        if(t.dx==dx && t.dy==dy)
            return false;
        return true;
    }
};
move src(10,10);
map  direction;
vector > all;
void init()
{
    //方向标识
    direction[move(x[0],y[0])]='n';        
    direction[move(x[1],y[1])]='s';        
    direction[move(x[2],y[2])]='e';        
    direction[move(x[3],y[3])]='w';        
    for(map::iterator it =direction.begin(); it != direction.end(); ++it)
    {
            cout<second;
    }

    //边界设定
    //第0行，0列,20行,20列为此次边界,不可访问
    for(int i=0;i<21;i++)
    {
        visited[0][i]=-1;    
        visited[i][0]=-1;
        visited[i][20]=-1;
        visited[20][i]=-1;
    }
}
namespace std
{
    ostream& operator<<(ostream& os,move t)
    {
//        os<        os<<"("<    }
}
//第一次移动不可能回到起点，所以结构上是直接循环，否则就要先决断了
//count为步长
void search(vector&  path,int a,int b,int max_lenth,int count,int change,int step,move last_move)
{
    if(count>max_lenth) return;
    int px,py,flag=0,pa=change,pb=step;
    //每一次休息,下一个方向不能与休息前方向相同
    if(count==change)
    {
        pa=count+step;
        pb=step+1;
        flag=1;
    }
    for(int i=0;i<4;i++)
    {
        move tmp(x[i],y[i]);
        if(flag && tmp==last_move)  //刚休息了，所以下个方向不能与前一个相同
        {
    //        cout<<"变化的点：("<            continue;
        }
        px=a+x[i];py=b+y[i];     //下面减枝
         //不经过同一个点1,施工地点不经过-1,到达边界-1,反正都不为0
        if(!visited[px][py])
        {
            cout<<"i="<            path.push_back(tmp);    
            visited[px][py]=1;

            search(path,px,py,max_lenth,count+1,pa,pb,tmp);

            //恢复现场
            visited[px][py]=0;
            path.pop_back();
        }else if(px==10 && py ==10){  //回到出发点等价于最后一点和起始点重合
            path.push_back(tmp);
            all.push_back(path);    
            cout<<"解决方案为："<            copy(path.begin(),path.end(),ostream_iterator(cout," "));
            cout<            path.pop_back();
        }
    }
}
main()
{
    init();
    visited[8][10]=-1; //施工,不可访问
    visited[16][8]=-1; //施工坐标
    vector path;
    visited[10][10]=1;
    search(path,10,10,8,0,1,2,move(2,2)); //8为最大长度
}

阅读(1228) | 评论(0) | 转发(0) |
0

上一篇：王伯买鱼问题

下一篇：输出比给定排列更大的所有排列(相当于STL算法 net_permutation的实现)

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6