农夫过河

  1 #include 
  2 #include 
  3 
  4 typedef int DataType;
  5 //顺序队列：类型和界面函数声明
  6 struct SeqQueue
  7 {// 顺序队列类型定义
  8     int MAXNUM; // 队列中最大元素个数
  9     int f, r;
 10     DataType *q;
 11 };
 12 
 13 typedef struct SeqQueue *PSeqQueue; // 顺序队列类型的指针类型
 14 
 15 //创建一个空队列
 16 PSeqQueue createEmptyQueue_seq(int m)
 17 {
 18     PSeqQueue queue = (PSeqQueue)malloc(sizeof(struct SeqQueue));
 19     if (queue != NULL)
 20     {
 21         queue->q = (DataType*)malloc(sizeof(DataType) *m);
 22         if (queue->q)
 23         {
 24             queue->MAXNUM = m;
 25             queue->f = 0;
 26             queue->r = 0;
 27             return (queue);
 28         }
 29         else
 30             free(queue);
 31     }
 32 
 33     printf("Out of space!!\n"); // 存储分配失败
 34     return NULL;
 35 }
 36 
 37 //判断队列是否为空
 38 int isEmptyQueue_seq(PSeqQueue queue)
 39 {
 40     return (queue->f == queue->r);
 41 }
 42 
 43 // 在队尾插入元素x，此队列队尾一个元素空出来
 44 void enQueue_seq(PSeqQueue queue, DataType x)
 45 {
 46     if ((queue->r + 1) % queue->MAXNUM == queue->f)
 47         printf("Full queue.\n");
 48     else
 49     {
 50         queue->q[queue->r] = x;
 51         queue->r = (queue->r + 1) % queue->MAXNUM;
 52     }
 53 }
 54 
 55 // 删除队列头部元素
 56 void deQueue_seq(PSeqQueue queue)
 57 {
 58     if (queue->f == queue->r)
 59         printf("Empty Queue.\n");
 60     else
 61         queue->f = (queue->f + 1) % queue->MAXNUM;
 62 }
 63 
 64 DataType frontQueue_seq(PSeqQueue queue)
 65 {
 66     if (queue->f == queue->r)
 67     {
 68         printf("Empty Queue.\n");
 69         return 0;
 70     }
 71     else
 72         return (queue->q[queue->f]);
 73 }
 74 
 75 
 76 //个体状态判断函数
 77 
 78 int farmer(int location)
 79 {
 80     //判断农夫的位置
 81     return (0 != (location &0x08));
 82 }
 83 
 84 int wolf(int location)
 85 {
 86     //判断狼的位置
 87     return (0 != (location &0x04));
 88 }
 89 
 90 int cabbage(int location)
 91 {
 92     //判断白菜的位置
 93     return (0 != (location &0x02));
 94 }
 95 
 96 int goat(int location)
 97 {
 98     //判断羊的位置
 99     return (0 != (location &0x01));
100 }
101 
102 //安全状态的判断函数
103 
104 // 若状态安全则返回true
105 int safe(int location)
106 {
107     // 羊吃白菜
108     if ((goat(location) == cabbage(location)) && (goat(location) != farmer(location)))
109         return 0;
110     // 狼吃羊
111     if ((goat(location) == wolf(location)) && (goat(location) != farmer(location)))
112         return 0;
113     return 1; // 其他状态是安全的
114 }
115 
116 void bin_print(int num)
117 {
118     char tmp[4];
119     int i;
120     for (i = 0; i < 4; ++i)
121     {
122         tmp[i] = num & 0x01;
123         num >>= 1;
124     }
125     for (i = 3; i >= 0; --i)
126         putchar((tmp[i] == 0)?'0':'1');
127     return;
128 }
129 
130 int main()
131 {
132 
133     int i, movers, location, newlocation;
134     int route[16]; //用于记录已考虑的状态路径
135     PSeqQueue moveTo; //用于记录可以安全到达的中间状态
136 
137     moveTo = createEmptyQueue_seq(20); //创建空队列
138     enQueue_seq(moveTo, 0x00); //初始状态进队列
139 
140     for (i = 0; i < 16; i++)
141         route[i] =  -1;
142 
143     //准备数组route初值
144     route[0] = 0;
145 
146     while (!isEmptyQueue_seq(moveTo) && (route[15] ==  - 1))
147     {
148         location = frontQueue_seq(moveTo); //取队头状态为当前状态
149         deQueue_seq(moveTo);
150 
151         //考虑各种物品移动
152         for (movers = 1; movers <= 8; movers <<= 1)
153             //农夫与移动的物品在同一侧
154             if ((0 != (location & 0x08)) == (0 != (location & movers)))
155             {
156                 newlocation = location ^ (0x08 | movers); //计算新状态
157 
158                 //新状态安全且未处理
159                 if (safe(newlocation) && (route[newlocation] ==  -1))
160                 {
161                     route[newlocation] = location; //记录新状态的前驱
162                     enQueue_seq(moveTo, newlocation); //新状态入队
163                 }
164             }
165     }
166 
167     // 打印出路径
168     if (route[15] !=  -1)
169         //到达最终状态
170     {
171         printf("The reverse path is : \n");
172 
173         for (location = 15; location >= 0; location = route[location])
174         {
175             printf("The location is : %2d, ", location);
176             bin_print(location);
177             putchar('\n');
178             if (location == 0)
179                 exit(0);
180         }
181     }
182     else
183         printf("No solution.\n");
184     return 0;
185 }