fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5.  
  6. #define BOX_NUM 2
  7. #define HISTORY_NUM_MAX 1024
  8.  
  9.  
  10. typedef struct
  11. {
  12. 	int capacity, volume;
  13. }box_t;
  14.  
  15.  
  16. typedef struct
  17. {
  18. 	box_t box[BOX_NUM];
  19. 	int times;
  20. 	int parent;
  21. }state_t;
  22.  
  23.  
  24. state_t history[HISTORY_NUM_MAX];
  25. int history_num=0;
  26.  
  27.  
  28. void history_clear(void)
  29. {
  30. 	memset(history, -1, sizeof(history));
  31. 	history_num=0;
  32. }
  33.  
  34.  
  35. int history_search(state_t *p)
  36. {
  37. 	int i;
  38.  
  39. 	for(i=0;i<history_num;i++)
  40. 	{
  41. 		if(memcmp(&history[i], p, sizeof(history[i].box))==0) return i;
  42. 	}
  43. 	return -1;
  44. }
  45.  
  46.  
  47. void history_add(state_t *p, int parent)
  48. {
  49. 	if(history_search(p)>=0) return;
  50.  
  51. 	if(history_num>=HISTORY_NUM_MAX)
  52. 	{
  53. 		printf("\nERROR : overflow\n");
  54. 		exit(1);
  55. 	}
  56. 	p->parent=parent;
  57. 	if(parent>=0)
  58. 	{
  59. 		p->times=history[parent].times+1;
  60. 	}
  61. 	else
  62. 	{
  63. 		p->times=0;
  64. 	}
  65. 	history[history_num++]=*p;
  66. }
  67.  
  68.  
  69. void box_fill(box_t *p)
  70. {
  71. 	p->volume=p->capacity;
  72. }
  73.  
  74.  
  75. void box_empty(box_t *p)
  76. {
  77. 	p->volume=0;
  78. }
  79.  
  80.  
  81. void box2box(box_t *to, box_t *from)
  82. {
  83. 	int volume1, volume2, move_volume;
  84.  
  85. 	volume1=from->volume;
  86. 	volume2=to->capacity-to->volume;
  87.  
  88. 	if(volume1<volume2) move_volume=volume1;
  89. 	else move_volume=volume2;
  90.  
  91. 	to->volume+=move_volume;
  92. 	from->volume-=move_volume;
  93. }
  94.  
  95.  
  96. int solve(void)
  97. {
  98. 	state_t work;
  99. 	int i, j, k;
  100.  
  101. 	for(i=0;i<history_num;i++)
  102. 	{
  103. 		if(history[i].box[0].volume==2 && history[i].box[1].volume==0) return i;
  104. 		for(j=0;j<BOX_NUM;j++)
  105. 		{
  106. 			work=history[i]; box_fill(&(work.box[j])); history_add(&work, i);
  107. 			work=history[i]; box_empty(&(work.box[j])); history_add(&work, i);
  108.  
  109. 			for(k=0;k<BOX_NUM;k++)
  110. 			{
  111. 				if(j==k) continue;
  112. 				work=history[i]; box2box(&(work.box[j]), &(work.box[k])); history_add(&work, i);
  113. 			}
  114. 		}
  115. 	}
  116. }
  117.  
  118.  
  119. void state_print(state_t *p)
  120. {
  121. 	int i, goukei=0;
  122.  
  123. 	for(i=0;i<BOX_NUM;i++)
  124. 	{
  125. 		goukei+=p->box[i].volume;
  126. 		printf("%dL=%d,", p->box[i].capacity, p->box[i].volume);
  127. 	}
  128. 	printf("Goukei=%d\n", goukei);
  129. }
  130.  
  131.  
  132. void result_print(int index)
  133. {
  134. 	if(index<0) return;
  135.  
  136. 	result_print(history[index].parent);
  137. 	state_print(&history[index]);
  138. }
  139.  
  140.  
  141. int main(void)
  142. {
  143. 	state_t initial={{{4,0},{3,0}}};
  144. 	int i, result;
  145.  
  146. 	history_clear();
  147. 	history_add(&initial, -1);
  148. 	result=solve();
  149.  
  150. 	result_print(result);
  151. 	return 0;
  152. }
  153.  
Success #stdin #stdout 0.01s 1744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4L=0,3L=0,Goukei=0
4L=0,3L=3,Goukei=3
4L=3,3L=0,Goukei=3
4L=3,3L=3,Goukei=6
4L=4,3L=2,Goukei=6
4L=0,3L=2,Goukei=2
4L=2,3L=0,Goukei=2
https://ideone.com/rFmiF
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!