fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct point{
  5.     int x,y,walk;
  6.     point() {};
  7.     point(int _x, int _y, int _walk) {
  8.         x = _x; y = _y; walk = _walk;
  9.     }
  10. };
  11.  
  12. struct lambang{
  13.     int x,y; char tanda;
  14.     lambang() {};
  15.     lambang(int _x, int _y, char _tanda) {
  16.         x = _x; y = _y; tanda = _tanda;
  17.     }
  18. };
  19.  
  20. point s,f,take;
  21. int nn,mm;
  22. char arr[1005][1005];
  23. bool flag[1005][1005];
  24. queue<point> q;
  25. vector<lambang> vec;
  26. bool bol;
  27.  
  28. void flood(int x, int y) {
  29.     if (bol) return;
  30.     if ((x>0)&&(y>0)&&(x<=nn)&&(y<=mm)) {
  31.         if (arr[x][y]=='T') {   cout<<take.walk<<endl; bol=true; return; }
  32.         if (((arr[x][y]=='#')||(arr[x][y]=='S'))&&(flag[x][y])) {
  33.             flag[x][y]=false;
  34.             flood(x+1,y);
  35.             flood(x-1,y);
  36.             flood(x,y+1);
  37.             flood(x,y-1);
  38.  
  39.             if (arr[x][y+1]=='.') vec.push_back(lambang(x,y+1,'2'));
  40.             if (arr[x][y-1]=='.') vec.push_back(lambang(x,y-1,'4'));
  41.             if (arr[x+1][y]=='.') vec.push_back(lambang(x+1,y,'3'));
  42.             if (arr[x-1][y]=='.') vec.push_back(lambang(x-1,y,'1'));
  43.         }
  44.     }
  45. }
  46.  
  47.  
  48. void straight(lambang t) {
  49.     if ((t.x>0)&&(t.y>0)&&(t.x<=nn)&&(t.y<=mm)) {
  50.         if ((arr[t.x][t.y]=='#')||(arr[t.x][t.y]=='T')) {
  51.             q.push(point(t.x,t.y,take.walk+1));
  52.             return;
  53.         }
  54.         if (t.tanda=='1')  straight(lambang(t.x-1,t.y,'1'));
  55.         if (t.tanda=='2')  straight(lambang(t.x,t.y+1,'2'));
  56.         if (t.tanda=='3')  straight(lambang(t.x+1,t.y,'3'));
  57.         if (t.tanda=='4')  straight(lambang(t.x,t.y-1,'4'));
  58.     }
  59. }
  60.  
  61. int main() {
  62.     string ss;
  63.     getline(cin,ss);
  64.     scanf("%d %d\n",&nn,&mm);
  65.     for(int i=0; i<=1002; i++) {
  66.         for(int j=0; j<=1002; j++) {
  67.             arr[i][j]='!';
  68.             flag[i][j]=false;
  69.         }
  70.     }
  71.     for(int i=1; i<=nn; i++)
  72.         for(int j=1; j<=mm; j++) {
  73.             cin>>arr[i][j];
  74.             flag[i][j]=true;
  75.             if (arr[i][j]=='S') s.x=i,s.y=j;
  76.             if (arr[i][j]=='T') f.x=i,f.y=j;
  77.         }  
  78.  
  79.     q.push(point(s.x,s.y,0));
  80.     memset(flag,true,sizeof(flag));
  81.     bol=false;
  82.     while (!q.empty()) {
  83.         take=q.front(); q.pop(); vec.clear();
  84.         if (arr[take.x][take.y]=='T') {
  85.             cout<<take.walk<<endl;
  86.             return 0;
  87.         }
  88.         flood(take.x,take.y);
  89.         if (bol) return 0;
  90.  
  91.         int size=vec.size();
  92.             for(int i=0; i<size; i++) {
  93.                 straight(vec[i]);
  94.             }
  95.         vec.clear();
  96.     }
  97.     printf("-1\n");
  98. }
Success #stdin #stdout 0s 5408KB
comments (?)
stdin
copy 
asd!!!!
6 5
S...#
.T.#.
.....
#..#.
.....
#...#
stdout
copy 
4
https://ideone.com/wzyKVA
language:
C++14 (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!