fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class Step {
  6.     public:
  7.     int i;
  8.     int j;
  9.     int lifes;
  10.  
  11.     Step(int i, int j, int lifes) {
  12.         this->i = i;
  13.         this->j = j;
  14.         this->lifes = lifes;
  15.     }
  16. };
  17.  
  18. typedef vector< vector<char> > Map;
  19. typedef vector<Step*> Steps;
  20.  
  21. bool mario(Map& m, Steps& s) {
  22. 	int i, j, lifes;
  23. 	int l=0, r=1;
  24. 	Step *p;
  25.  
  26. 	while (l < r) {
  27. 		p = s[l++];
  28. 		//cout << p->i << " " << p->j << " " << p->lifes << " " << m[p->i][p->j] << endl;
  29.  
  30. 		lifes = p->lifes;
  31. 	    if (lifes < 0)
  32. 	        return false;
  33.  
  34. 	    i = p->i;
  35. 	    j = p->j;
  36.  
  37. 	    if (m[i][j] == 'x')
  38. 	        continue;
  39.  
  40. 	    if (m[i][j] == 'T') 
  41. 			return true;
  42.  
  43. 	    m[i][j] = 'x';
  44. 	    lifes--;
  45. 	    s.emplace_back(new Step(i-1, j, lifes));
  46. 	    s.emplace_back(new Step(i, j+1, lifes));
  47. 	    s.emplace_back(new Step(i+1, j, lifes));
  48. 	    s.emplace_back(new Step(i, j-1, lifes));
  49. 	    r += 4;
  50. 	}
  51.     return false;
  52. }
  53.  
  54. int main() {
  55.     int h, w;
  56.     cin >> h >> w;
  57.  
  58.     Map matrix(h+2, vector<char>(w+2));
  59.  
  60.     int i, j;
  61.     int x, y;
  62.  
  63.     for (i=1; i<=h; i++) {
  64.         for (j=1; j<=w; j++) {
  65.             cin >> matrix[i][j];
  66.             if (matrix[i][j] == 'S') {
  67.                 x = i;
  68.                 y = j;
  69.             }
  70.         }
  71.         matrix[i][0] = 'x';
  72.         matrix[i][j] = 'x';
  73.     }
  74.  
  75.     for (j=1; j<=w; j++) {
  76.         matrix[0][j] = 'x';
  77.         matrix[i][j] = 'x';
  78.     }
  79.  
  80.     int lifes;
  81.     cin >> lifes;
  82.  
  83.     Steps s;
  84.     s.emplace_back(new Step(x, y, lifes*4));
  85.  
  86.     if (mario(matrix, s))
  87.         cout << "SIM\n";
  88.     else
  89.         cout << "NAO\n";
  90.  
  91.     return 0;
  92. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
1 6
.S...T
1
stdout
copy 
SIM
https://ideone.com/s0mC3g
language:
C++ (gcc 8.3)
created:
6 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!