fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <tuple>
  4. #define INF 2100000000
  5. using namespace std;
  6.  
  7. int N;
  8. int table[101][101];
  9. int ret[101][101];
  10. int dx[4] = { 0, 0, 1, -1 };
  11. int dy[4] = { 1, -1, 0, 0 };
  12.  
  13. int main(void)
  14. {
  15. 	ios_base::sync_with_stdio(0);
  16. 	cin.tie(0);
  17. 	cout.tie(0);
  18.  
  19. 	cin >> N;
  20. 	for (int i = 1; i <= N; i++)
  21. 	{
  22. 		for (int j = 1; j <= N; j++)
  23. 		{
  24. 			cin >> table[i][j];
  25. 			ret[i][j] = INF;
  26. 		}
  27. 	}
  28.  
  29. 	//최대 - 최소, 최대, 최소, x, y
  30. 	queue<tuple<int, int, int, int, int>> q;
  31. 	q.push({ 0, table[1][1], table[1][1], 1, 1 });
  32. 	ret[1][1] = 1;
  33.  
  34. 	while (!q.empty())
  35. 	{
  36. 		int sub, maxi, mini, x, y;
  37. 		tie(sub, maxi, mini, x, y) = q.front();
  38. 		q.pop();
  39.  
  40. 		for (int i = 0; i < 4; i++)
  41. 		{
  42. 			int nx = x + dx[i];
  43. 			int ny = y + dy[i];
  44. 			int nmaxi = max(maxi, table[nx][ny]);
  45. 			int nmini = min(mini, table[nx][ny]);
  46. 			int nsub = nmaxi - nmini;
  47.  
  48. 			if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
  49. 			if (ret[nx][ny] > nsub)
  50. 			{
  51. 				ret[nx][ny] = nsub;
  52. 				q.push({ nsub, nmaxi, nmini, nx, ny });
  53. 			}
  54.  
  55. 		}
  56. 	}
  57. 	cout << ret[N][N] << endl;
  58.  
  59. }
  60.  
  61.  
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin
copy 
5
5 5 5 0 0
5 0 5 0 0
5 0 4 0 0
5 0 5 5 8
5 5 7 0 5
stdout
copy 
4
https://ideone.com/iyyzLH
language:
C++14 (gcc 8.3)
created:
1 year 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!