fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstdio>
  4. using namespace std;
  5. int R, C; // R 세로 C 가로
  6. char map[51][51];
  7. int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 };
  8. queue <pair<pair<int, int>, int> > q;
  9. queue <pair<int, int> > w;
  10. void bfs() {
  11. 	while (!q.empty()) {
  12. 		int x, y, cnt; 
  13. 		int wx, wy, ws;
  14. 		x = q.front().first.second;
  15. 		y = q.front().first.first;
  16. 		cnt = q.front().second;
  17. 		q.pop();
  18. 		ws = w.size();
  19. 		for (int i = 0; i < ws; i++) {
  20. 			wx = w.front().second;
  21. 			wy = w.front().first;
  22. 			w.pop();
  23. 			for (int i = 0; i < 4; i++) {
  24. 				int wdx, wdy;
  25. 				wdx = wx + dx[i];
  26. 				wdy = wy + dy[i];
  27. 				if (wdy >= 0 && wdy < R && wdx >= 0 && wdx < C && map[wdy][wdx] != 'X' && map[wdy][wdx] != 'D' && map[wdy][wdx] != '*') {
  28. 					map[wdy][wdx] = '*';
  29. 					w.push({ wdy,wdx });
  30. 				}
  31. 			}
  32. 		}
  33. 		for (int i = 0; i < 4; i++) {
  34. 			int nx, ny;
  35. 			nx = x + dx[i];
  36. 			ny = y + dy[i];
  37. 			if (nx >= 0 && nx < C && ny >= 0 && ny < R && map[ny][nx] != '*' && map[ny][nx] != 'X') {
  38. 				if (map[ny][nx] == 'D') {
  39. 					cout << cnt + 1 << endl;
  40. 					return ;
  41. 				}
  42. 				else {
  43. 					map[ny][nx] = 'S';
  44. 					q.push({ { ny,nx }, cnt + 1 });
  45. 				}
  46. 			}
  47.  
  48. 		}
  49. 	}
  50. 	cout << "KAKTUS" << endl;
  51. }
  52. int main() {
  53. 	cin >> R >> C;
  54. 	for (int i = 0; i < R; i++) {
  55. 		for (int j = 0; j < C; j++) {
  56. 			cin >> map[i][j];
  57. 			if (map[i][j] == 'S') q.push({ { i,j }, 0 });
  58. 			if (map[i][j] == '*') w.push({ i,j });
  59. 		}
  60. 	}
  61. 	bfs();
  62. }
Time limit exceeded #stdin #stdout 5s 4333568KB
comments (?)
stdin
copy 
50 50
D.................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
..................................................
.................................................S
stdout
copy 
Standard output is empty
https://ideone.com/8W12qc
language:
C++14 (gcc 8.3)
created:
5 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!