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