fork(3) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> graf[1000007];
  5. bool odwiedzony[1000007];
  6. int warstwa[1000007];
  7.  
  8. int main() {
  9. 	int n, m, S, a, b;
  10. 	cin >> n >> m;
  11. 	for(int i = 1; i <=n*m; i++){
  12. 		int opcja1 = i-1;
  13. 		int opcja2 = i+1;
  14. 		int opcja3 = i-m;
  15. 		int opcja4 = i+m;
  16. 		if(opcja1 >= 1 && opcja1 <= n*m){
  17. 			graf[i].push_back(opcja1);
  18. 		}
  19. 		if(opcja2 >= 1 && opcja2 <= n*m){
  20. 			graf[i].push_back(opcja2);
  21. 		}
  22. 		if(opcja2 >= 1 && opcja1 <= n*m){
  23. 			graf[i].push_back(opcja2);
  24. 		}
  25. 		if(opcja3 >= 1 && opcja3 <= n*m){
  26. 			graf[i].push_back(opcja3);
  27. 		}
  28. 		if(opcja4 >= 1 && opcja4 <= n*m){
  29. 			graf[i].push_back(opcja4);
  30. 		}
  31. 	}
  32. 	cin >> S;
  33. 	queue<int> Q;
  34. 	for(int i = 0; i < S; i++){
  35. 		cin >> a >> b;
  36. 		//wrzuæ do kolejki
  37. 		Q.push((a*m)-(m-b));
  38. 		odwiedzony[(a*m)-(m-b)] = true;
  39. 	}
  40. 	//BFS
  41. 	while (not(Q.empty())) {
  42. 		int v = Q.front();
  43. 		Q.pop();
  44. 		for (int sasiad : graf[v]) {
  45.     		if (not(odwiedzony[sasiad])) {
  46.     			odwiedzony[sasiad] = true;
  47.     			Q.push(sasiad);
  48.     			warstwa[sasiad] = warstwa[v] + 1;
  49.     		}
  50. 		}
  51. 	}
  52. 	for(int i = 1; i <= n*m; i++){
  53. 		cout << warstwa[i] << " ";
  54. 		if(i % m == 0){
  55. 			cout << "\n";
  56. 		}
  57. 	}
  58. 	return 0;
  59. }
Success #stdin #stdout 0.01s 27056KB
comments (?)
stdin 
6 5
2
2 4
6 1
stdout 
4 3 2 1 2 
3 2 1 0 1 
2 3 2 1 2 
2 3 3 2 2 
1 2 3 2 1 
0 1 2 3 2
https://ideone.com/NRtB3H
language:
C++14 (gcc 8.3)
created:
4 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!