fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // N x N matrix
  5. #define N 6
  6.  
  7. // Function to check if cell (i, j) is a valid cell or not
  8. bool isValid(int i, int j)
  9. {
  10. 	return (i >= 0 && i < N && j >= 0 && j < N);
  11. }
  12.  
  13. // Find length of longest path starting from cell (i, j) formed by  
  14. // adjacent numbers in the matrix
  15. int findLongestPath(int mat[N][N], int i, int j)
  16. {
  17. 	// if the cell is invalid
  18. 	if (!isValid (i, j))
  19. 		return 0;
  20.  
  21. 	// to store length of path starting (i, j)
  22. 	int len = 0;
  23.  
  24. 	// recurse top cell if its value is +1 of value at (i, j)
  25. 	if (i > 0 && mat[i - 1][j] - mat[i][j] == 1)
  26. 		len = findLongestPath(mat, i - 1, j);
  27.  
  28. 	// recurse right cell if its value is +1 of value at (i, j)
  29. 	if (j + 1 < N && mat[i][j + 1] - mat[i][j] == 1)
  30. 		len = findLongestPath(mat, i, j + 1);
  31.  
  32. 	// recurse bottom cell if its value is +1 of value at (i, j)
  33. 	if (i + 1 < N && mat[i + 1][j] - mat[i][j] == 1)
  34. 		len = findLongestPath(mat, i + 1, j);
  35.  
  36. 	// recurse left cell if its value is +1 of value at (i, j)
  37. 	if (j > 0 && mat[i][j - 1] - mat[i][j] == 1)
  38. 		len = findLongestPath(mat, i, j - 1);
  39.  
  40. 	// note that as matrix contains all distinct elements,
  41. 	// there is only one path possible from current cell
  42.  
  43. 	// return length of path starting from (i, j)
  44. 	return 1 + len;
  45. }
  46.  
  47. // main function
  48. int main()
  49. {
  50. 	int mat[N][N] = 
  51. 	{ 
  52. 		{ 10, 13, 14, 21, 23 },
  53. 		{ 11,  9, 22,  2,  3 },
  54. 		{ 12,  8,  1,  5,  4 },
  55. 		{ 15, 24,  7,  6, 20 },
  56. 		{ 16, 17, 18, 19, 25 }
  57. 	};
  58.  
  59. 	// stores the length of longest path found so far
  60. 	int result = 1;
  61.  
  62. 	// from each cell (i, j), find the longest path starting from it
  63. 	for (int i = 0; i < N; i++) 
  64. 		for (int j = 0; j < N; j++) 
  65. 			result = max(result, findLongestPath(mat, i, j));
  66.  
  67. 	// print the length of longest path
  68. 	cout << "Length of longest sequence is " << result;
  69.  
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Length of longest sequence is 6
https://ideone.com/EOO3Gy
Find length of longest path formed by adjacent numbers in the matrix
language:
C++14 (gcc 8.3)
created:
7 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!