fork download 
  1. #include <iostream>
  2.  
  3. const int N_MAX = 100;
  4. const int M_MAX = 100;
  5. const int NM_MAX = N_MAX * M_MAX;
  6. const int H_MAX = 10000;
  7. const int INFTY = 65535;
  8.  
  9. using namespace std;
  10.  
  11. struct t_coords
  12. {
  13. 	char x;
  14. 	char y;
  15. };
  16.  
  17. struct t_heap
  18. {
  19. 	t_coords data[NM_MAX];
  20. 	unsigned int size;
  21. };
  22.  
  23. struct t_square
  24. {
  25. 	unsigned int h;
  26. 	unsigned int l_path;
  27. };
  28.  
  29. // p_queue_elem moze tutaj blad??
  30. struct t_queue_elem
  31. {
  32. 	t_coords coords;
  33. 	t_queue_elem* next;
  34. };
  35.  
  36. struct t_queue
  37. {
  38. 	t_queue_elem *first;
  39. 	t_queue_elem *last ;
  40. };
  41.  
  42. t_square board[N_MAX+1][M_MAX+1];
  43. unsigned int n,m;
  44. t_queue queue;
  45. t_heap heap;
  46.  
  47. void queue_init(t_queue q)
  48. {
  49. 	q.first = NULL;
  50. 	q.last = NULL;
  51. }
  52.  
  53. void queue_put(char x, char y, t_queue q)
  54. {
  55. 	t_queue_elem *p = new t_queue_elem;
  56.  
  57. 	p->coords.x = x;
  58. 	p->coords.y = y;
  59.     p->next = NULL;
  60.  
  61.    if (q.first == NULL)
  62.    {
  63.       q.first = p;
  64.    }
  65.    else
  66.    {
  67. 	   q.last->next = p;
  68.    }
  69.    q.last = p;	
  70. }
  71.  
  72. void queue_get(char x, char y, t_queue q)
  73. {
  74. 	t_queue_elem *p = new t_queue_elem();
  75.  
  76. 	x = q.first->coords.x;
  77. 	y = q.first->coords.y;
  78.  
  79. 	p = q.first;
  80. 	q.first = q.first->next;
  81. 	if(q.first == NULL)
  82. 	{
  83. 		q.last = NULL;
  84. 	}
  85. 	delete p;
  86. }
  87.  
  88. bool queue_empty(t_queue q)
  89. {
  90. 	if(q.first == NULL)
  91. 	{
  92. 		return true;
  93. 	}
  94. 	else
  95. 	{
  96. 		return false;
  97. 	}
  98. }
  99.  
  100. unsigned int height(t_coords c)
  101. {
  102. 	return board[c.x][c.y].h;
  103. }
  104.  
  105. void heap_init(t_heap h)
  106. {
  107. 	h.size = 0;
  108. }
  109.  
  110. void heap_swap(t_heap h, unsigned int i, unsigned int j)
  111. {
  112. 	t_coords c;
  113.  
  114. 	c = h.data[i];
  115. 	h.data[i] = h.data[j];
  116. 	h.data[j] = c;
  117. }
  118.  
  119. void heap_go_down(t_heap h)
  120. {
  121. 	unsigned int i, smallest;
  122.  
  123. 	i = 1;
  124. 	while(2*i <= h.size)
  125. 	{
  126. 		if(2*i <= h.size && height(h.data[2*i]) < height(h.data[i]))
  127. 		{
  128. 			smallest = 2*i;
  129. 		}
  130. 		else
  131. 		{
  132. 			smallest = i;
  133. 		}
  134. 		if(2*i + 1 <= h.size && height(h.data[2*i+1]) < height(h.data[smallest]))
  135. 		{
  136. 			smallest = 2 * i + 1;
  137. 		}
  138. 		if(smallest != i)
  139. 		{
  140. 			heap_swap(h,smallest,i);
  141. 		}
  142. 		else
  143. 		{
  144. 			break;
  145. 		}
  146. 	}
  147. }
  148.  
  149. void heap_add(t_heap h, char x, char y)
  150. {
  151. 	unsigned int i;
  152. 	h.size++;
  153. 	i = h.size;
  154.  
  155. 	while( i > 1 && board[x][y].h <  height( h.data[i/2]))
  156. 	{
  157. 		h.data[i] = h.data[i/2];
  158. 		i = i/2;
  159. 	}
  160. 	h.data[i].x = x;
  161. 	h.data[i].y = y;
  162. }
  163.  
  164. void heap_remove( t_heap h, char x, char y)
  165. {
  166. 	x = h.data[1].x;
  167. 	y = h.data[1].y;
  168. 	h.data[1] = h.data[h.size];
  169. 	h.size--;
  170. 	heap_go_down(h);
  171. }
  172.  
  173. bool heap_empty(t_heap h)
  174. {
  175. 	if(h.size == 0)
  176. 	{
  177. 		return true;
  178. 	}
  179. 	else
  180. 	{
  181. 		return false;
  182. 	}
  183. }
  184.  
  185.  
  186. // indeksy odwrocic m z n ??
  187. // zle wczytanie danych ??
  188. void read_data()
  189. {
  190. 	unsigned int w,h;
  191. 	cin >> n;
  192. 	cin >> m;
  193. 	heap_init(heap);
  194.  
  195. 	for(int i = 0; i <= n + 1; i++)
  196. 	{
  197.          board[i][0].h = INFTY; 
  198. 		 board[i][0].l_path = INFTY;
  199.          board[i][m + 1].h = INFTY; 
  200. 		 board[i][m + 1].l_path = INFTY;
  201. 	}
  202.  
  203. 	for(int j = 0; j <= m + 1; j++)
  204. 	{
  205.          board[0][j].h = INFTY; 
  206. 		 board[0][j].l_path = INFTY;
  207.          board[n + 1][j].h = INFTY; 
  208. 		 board[n + 1][j].l_path = INFTY;
  209. 	}
  210.  
  211. 	for(int i = 1; i <= n; i++)
  212. 	{
  213.       for(int j = 1; j <= m; j++)
  214. 	  {
  215.         board[i][j].l_path = INFTY;
  216. 		cin >> board[i][j].h;
  217.         heap_add( heap, i, j);
  218. 	  }
  219. 	}
  220. }
  221.  
  222. void adjust_lpath(char x, char y, unsigned int value)
  223. {
  224. 	if(board[x][y].h <= value && board[x][y].l_path == INFTY)
  225. 	{
  226. 		board[x][y].l_path = value;
  227. 		queue_put(x,y,queue);
  228. 	}
  229. }
  230.  
  231.  
  232. void find_paths()
  233. {
  234. 	char x,y;
  235. 	x=1;
  236. 	y=1;
  237. 	t_queue_elem p;
  238.  
  239. 	queue_init(queue);
  240.  
  241. 	do
  242. 	{
  243. 		heap_remove(heap, x, y);
  244. 		if(x == 1 || x == n ||y == 1 || y == m || board[x-1][y].l_path < INFTY
  245. 			|| board[x+1][y].l_path < INFTY
  246. 			|| board[x][y-1].l_path < INFTY
  247. 			|| board[x][y+1].l_path < INFTY)
  248. 		{
  249. 			adjust_lpath( x, y, board[x][y].h);
  250. 		}
  251.  
  252. 		while(!queue_empty(queue))
  253. 		{
  254. 			queue_get(x, y, queue);
  255.             adjust_lpath( x - 1, y, board[x][y].l_path);
  256.             adjust_lpath( x + 1, y, board[x][y].l_path);
  257.             adjust_lpath( x, y - 1, board[x][y].l_path);
  258.             adjust_lpath( x, y + 1, board[x][y].l_path);
  259. 		}
  260. 	}while(!heap_empty(heap));
  261. }
  262.  
  263. long int sum_up()
  264. {
  265. 	char i,j;
  266. 	long int sum;
  267.  
  268. 	sum = 0;
  269. 	for(i = 1; i <= n; i++)
  270. 	{
  271. 		for(j = 1; j <= m; j++)
  272. 		{
  273. 			sum += (board[i][j].l_path - board[i][j].h);
  274. 		}
  275. 	}
  276. 	return sum;
  277. }
  278. int main()
  279. {
  280. 	read_data();
  281.  
  282. 	find_paths();
  283.  
  284. 	cout << sum_up();
  285.  
  286. 	system("PAUSE");
  287. 	return 0;
  288. }
Success #stdin #stdout #stderr 0s 3532KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
sh: PAUSE: not found
https://ideone.com/jZAHYn
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!