fork(1) download
copy 
  1. #include <stdio.h>
  2.  
  3. int test[1000][1000]={0}, n,dp[1000][1000]={0},p,q,r,s,w[1000][1000],x[1000][1000],y[1000][1000],z[1000][1000];
  4. int maze[1000][1000];
  5.  
  6. int min(int a,int b)
  7. {
  8.     return (a<b)?a:b;
  9. }
  10. int path(int i, int j){
  11. test[i][j] = 1;
  12. if(i==r && j==s)
  13. {
  14.     test[i][j]=0;
  15.     return 0;
  16. }
  17. if(dp[i][j]!=0)
  18.     {
  19.         test[i][j]=0;
  20.         return dp[i][j];
  21.     }
  22. else
  23. {
  24. if((j + 1) <= n && test[i][j + 1] == 0 && maze[i][j + 1] == 0)
  25. w[i][j]=1+path(i, j + 1);
  26. else w[i][j]=99999;
  27. if((i + 1) <= n && test[i + 1][j] == 0 && maze[i + 1][j] == 0)
  28. x[i][j]=1+path(i + 1, j);
  29. else x[i][j]=99999;
  30. if((j - 1) >= 1 && test[i][j - 1] == 0 && maze[i][j - 1] == 0)
  31. y[i][j]=1+path(i, j - 1);
  32. else y[i][j]=99999;
  33. if((i - 1) >= 1 && test[i - 1][j] == 0 && maze[i - 1][j] == 0)
  34. z[i][j]=1+path(i - 1, j);
  35. else z[i][j]=99999;
  36. }
  37. test[i][j]=0;
  38. dp[i][j]=min(min(w[i][j],x[i][j]),min(y[i][j],z[i][j]));
  39. return dp[i][j];
  40. }
  41.  
  42.  
  43. int main(){
  44. int i, j,ans;
  45.  
  46. scanf("%d",&n);
  47. for(i = 1;i <= n;i++){
  48. for(j = 1;j <= n;j++){
  49. scanf("%d", &maze[i][j]);
  50. if(maze[i][j]==9){r=i;s=j;}
  51.  
  52. }
  53. }
  54. ans=path(1,1);
  55. if(ans>900)ans=0;
  56. printf("%d\n",ans);
  57. return 0;
  58. }
  59.  
Success #stdin #stdout 0s 29640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/0SJy3m
language:
C (gcc 8.3)
created:
9 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!