fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef pair<int, int> pii;
  6. const int MX = 500;
  7. const int INF = 1e9 + 10;
  8. int r, c, vis[MX][MX];
  9. int dx[] = {0, 0, 1, -1};
  10. int dy[] = {1, -1, 0, 0};
  11.  
  12. void init(){
  13. 	for(int i = 0; i < MX; i++){
  14. 		for(int j = 0; j < MX; j++){
  15. 			vis[i][j] = INF;
  16. 		}
  17. 	}
  18. }
  19.  
  20. bool isValid(int x, int y){
  21. 	return (x >= 0 && x < r && y >= 0 && y < c);
  22. }
  23.  
  24. void bfs(vector <string> maze){
  25. 	vis[0][0] = 0;
  26. 	queue<pii> q;
  27. 	q.push(pii(0, 0));
  28.  
  29. 	for(; !q.empty() ;){
  30. 		int ux = q.front().first;
  31. 		int uy = q.front().second;
  32. 		q.pop();
  33.  
  34. 		for(int i = 0; i < 4; i++){
  35. 			int vx = ux + dx[i];
  36. 			int vy = uy + dy[i];
  37.  
  38. 			if(!isValid(vx, vy)) continue;
  39. 			if(maze[vx][vy] == '#' || vis[vx][vy] != INF) continue;
  40. 			vis[vx][vy] = vis[ux][uy] + 1;
  41. 			q.push(pii(vx, vy));
  42. 		}
  43. 	}
  44. }
  45.  
  46. string canWin(vector <string> maze, int k) {
  47. 	r = maze.size();
  48. 	c = maze[0].size();
  49. 	init();
  50. 	bfs(maze);
  51.     return (vis[r - 1][c - 1] <= k) ? "Fahad wins" : "Better luck next time";
  52. }
  53.  
  54. int main(){
  55. 	int n, k;
  56. 	string line;
  57. 	vector <string> maze;
  58.  
  59. 	cin >> n;
  60. 	for(int i = 0; i < n; i++){
  61. 		cin >> line;
  62. 		maze.push_back(line);
  63. 	}
  64. 	cin >> k;
  65. 	cout << canWin(maze, k) << endl;
  66. 	return 0;
  67. }
Success #stdin #stdout 0s 17048KB
comments (?)
stdin
copy 
2
..
..
3
stdout
copy 
Fahad wins
https://ideone.com/iQyyBU
language:
C++14 (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!