fork download
copy 
  1. #include <iostream>
  2. #include <math.h>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. #define Du 2147483647
  7.  
  8. int n;
  9. char arr[1003][1003];
  10. void read ()
  11. {
  12.     cin>>n;
  13.     for (int i=1; i<=n; i++)
  14.     {
  15.         for (int j=1; j<=n; j++)
  16.         {
  17.             cin>>arr[i][j];
  18.         }
  19.     }
  20. }
  21.  
  22. long long F[1003][1003];
  23. int check[1003][1003];
  24. void init()
  25. {
  26.     for (int i=0; i<=n; i++)
  27.     {
  28.         for (int j=0; j<=n; j++)
  29.         {
  30.             F[i][j] = 0;
  31.             check[i][j]=0;
  32.         }
  33.     }
  34. }
  35. long long count ()
  36. {
  37.     F[1][0]=1;
  38.     for (int i=1; i<=n; i++)
  39.     {
  40.         for (int j=1; j<=n; j++)
  41.         {
  42.             if (arr[i][j]=='.')
  43.                 F[i][j]=(F[i-1][j]+F[i][j-1])%Du;
  44.         }
  45.     }
  46.     return F[n][n];
  47. }
  48.  
  49. struct data
  50. {
  51.     int i;
  52.     int j;
  53. };
  54.  
  55. int x_xq[]={-1, +0, +1, +0};
  56. int y_xq[]={+0, +1, +0, -1};
  57.  
  58.  
  59. void BFS (int y, int x)
  60. {
  61.     data tmp;
  62.     tmp.i = y;
  63.     tmp.j = x;
  64.     queue <data> q;
  65.     q.push(tmp);
  66.     check[y][x]=1;
  67.     while (!q.empty())
  68.     {
  69.         data u = q.front();
  70.         q.pop();
  71.         for (int i=0; i<4; i++)
  72.         {
  73.             int x_m = u.j+x_xq[i];
  74.             int y_m = u.i+y_xq[i];
  75.             if (x_m>=1 && x_m<=n && y_m>=1 && y_m<=n && check[y_m][x_m]==0 && arr[y_m][x_m]=='.')
  76.             {
  77.                 tmp.i = y_m;
  78.                 tmp.j = x_m;
  79.                 q.push(tmp);
  80.                 check[y_m][x_m] = 1;
  81.             }
  82.         }
  83.     }
  84. }
  85.  
  86. int main ()
  87. {
  88.     read();
  89.     init();
  90.     long long x = count();
  91.     if (x!=0)
  92.         cout<<x;
  93.     else
  94.     {
  95.         BFS(1, 1);
  96.         if (check[n][n]==1)
  97.             cout<<"THE GAME IS A LIE";
  98.         else
  99.             cout<<"INCONCEIVABLE";
  100.     }
  101.     return 0;
  102. }
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
5
.....
#..#.
#..#.
...#.
.....
stdout
copy 
6
https://ideone.com/D94X0C
v- BCROBOT - Đường đi rô-bốt
language:
C++ (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!