fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, M, n, m;
  5. int visited[1000][1000];
  6. int grid[1000][1000];
  7. int dx[] = {0, 1, 0, -1};
  8. int dy[] = {1, 0, -1, 0};
  9.  
  10. int ff(int x, int y, int dist) { // DFS
  11. 	if(visited[x][y] != -1) return 0;
  12. 	visited[x][y] = dist;
  13. 	for(int i = 0; i < 4; i++) {
  14. 		int xx = x+dx[i];
  15. 		int yy = y+dy[i];
  16. 		if(xx >= 0 && xx < N && yy >= 0 && yy < M && grid[xx][yy] == 0)
  17. 			ff(xx, yy, dist+1);
  18. 	}
  19. 	return 0;
  20. }
  21.  
  22. int main() {
  23. 	cin >> N >> M;
  24. 	for(int i = 0; i < N; i++)
  25. 		for(int j = 0; j < M; j++)
  26. 			cin >> grid[i][j];
  27. 	cin >> n >> m;
  28. 	for(int i = 0; i < N; i++)
  29. 		for(int j = 0; j < M; j++)
  30. 			visited[i][j] = -1;
  31. 	// ff(n-1, m-1, 0);
  32. 	queue<pair<pair<int, int>, int> > q;
  33. 	q.push(make_pair(make_pair(n-1, m-1), 1));
  34. 	while(!q.empty()) {
  35. 		int x = q.front().first.first;
  36. 		int y = q.front().first.second;
  37. 		int dist = q.front().second;
  38. 		q.pop();
  39. 		if(visited[x][y] != -1) continue;
  40. 		visited[x][y] = dist;
  41. 		for(int i = 0; i < 4; i++) {
  42. 			int xx = x+dx[i];
  43. 			int yy = y+dy[i];
  44. 			if(xx >= 0 && xx < N && yy >= 0 && yy < M && grid[xx][yy] == 0)
  45. 				q.push(make_pair(make_pair(xx, yy), dist+1));
  46. 		}
  47. 	}
  48.  
  49. 	for(int i = 0; i < N; i++) {
  50. 		for(int j = 0; j < M; j++)
  51. 			printf("%2d ", visited[i][j]);
  52. 		cout << endl;
  53. 	}
  54. 	return 0;
  55. }
Success #stdin #stdout 0.01s 5864KB
comments (?)
stdin
copy 
8 10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 0 0 -1 0 0 0
-1 0 0 -1 -1 0 0 0 -1 -1
-1 -1 0 0 -1 -1 -1 0 0 -1
-1 0 0 0 -1 0 -1 -1 -1 -1
-1 0 -1 0 -1 0 -1 0 0 -1
-1 0 -1 0 0 0 0 0 -1 -1
-1 0 -1 -1 -1 -1 -1 -1 -1 -1
7 5
stdout
copy 
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 
-1  9  8  9 10 11 -1 15 16 17 
-1  8  7 -1 -1 12 13 14 -1 -1 
-1 -1  6  5 -1 -1 -1 15 16 -1 
-1  6  5  4 -1  4 -1 -1 -1 -1 
-1  7 -1  3 -1  3 -1  5  6 -1 
-1  8 -1  2  1  2  3  4 -1 -1 
-1  9 -1 -1 -1 -1 -1 -1 -1 -1
https://ideone.com/maItZM
language:
C++ (gcc 8.3)
created:
12 days 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!