fork(1) download
  1. // Longest path on a grid
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std ;
  6. typedef long long ll ;
  7.  
  8. int n, m ;
  9. bool visited[10][10] ;
  10.  
  11. int ff(int x1, int y1, int x2, int y2){
  12.  
  13. /*if(x1 or x2 is out of bounds or visited before)
  14. return -INF (inf can be 100 as the grid is low in area)*/
  15. if(x1 >= n || y1 >= m || x1 < 0 || y1 < 0 || visited[x1][y1])
  16. return -100 ;
  17.  
  18. if(x1 == x2 && y1 == y2)
  19. return 0 ;
  20.  
  21. visited[x1][y1] = 1 ;
  22.  
  23. int v1 = 1 + ff(x1 + 1, y1, x2, y2) ;
  24. int v2 = 1 + ff(x1, y1 + 1, x2, y2) ;
  25. int v3 = 1 + ff(x1 - 1, y1, x2, y2) ;
  26. int v4 = 1 + ff(x1, y1 - 1, x2, y2) ;
  27.  
  28. visited[x1][y1] = 0 ;
  29.  
  30. return max( max(v1, v2) , max(v3, v4) ) ;
  31.  
  32. }
  33.  
  34. // also print the path? can be multiple paths though
  35. void solve(){
  36.  
  37. for(int i = 0 ; i < 10 ; i++)
  38. for(int j = 0 ; j < 10 ; j++)
  39. visited[i][j] = 0 ;
  40.  
  41. cin >> n >> m ;
  42. int x1, y1, x2, y2 ; cin >> x1 >> y1 >> x2 >> y2 ;
  43.  
  44. string mat[n] ;
  45. for(int i = 0 ; i < n ; i++) cin >> mat[i] ;
  46. for(int i = 0 ; i < n ; i++)
  47. for(int j = 0 ; j < m ; j++)
  48. if(mat[i][j] == '#')
  49. visited[i][j] = 1 ;
  50.  
  51. int ans = ff(x1, y1, x2, y2) ;
  52.  
  53. if(ans < 0)
  54. cout << "-1\n" ;
  55. else
  56. cout << ans << "\n" ;
  57.  
  58. }
  59.  
  60. int main(){
  61.  
  62. #ifndef ONLINE_JUDGE
  63. freopen("sample input.txt", "r", stdin) ;
  64. freopen("output.txt", "w", stdout) ;
  65. #endif
  66.  
  67. ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
  68.  
  69. int t ; cin >> t ;
  70. while(t--) solve() ;
  71.  
  72. return 0 ;
  73. }
  74.  
Success #stdin #stdout 0s 15240KB
stdin
4
1 5
0 1 0 0
.....
2 3
0 0 1 2
...
.#.
5 2
4 0 0 0
..
#.
.#
..
..
5 5
1 2 4 0
.....
.....
.....
.....
.....
stdout
1
3
-1
23