fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define pii pair <int, int>
  5. const int maxn = (int)1e3 + 1, max_ = (int)1e5 + 1, INF = (int)1e9;
  6. int n, m;
  7. vector < vector <int> > a(maxn + 1, vector <int> (maxn + 1));
  8. vector < vector <int> > d(maxn + 1, vector <int> (maxn + 1, INF));
  9. vector <int> ans(max_ + 10, 0);
  10. int dx[] = {1, 0}, dy[] = {0, 1};
  11.  
  12. void sieve()
  13. {
  14. 	for (int i = 2; i <= max_; i++)
  15. 	{
  16. 		for (int j = i; j <= max_; j += i)
  17. 		{
  18. 			ans[j]++;
  19. 		}
  20. 	}
  21. }
  22.  
  23. void dijkstra(int i, int j)
  24. {
  25. 	d[i][j] = ans[a[i][j]];
  26. 	priority_queue <pair <pii, int>, vector < pair <pii, int> >, greater < pair <pii, int> >> pq;
  27. 	pq.push({{i, j}, ans[a[i][j]]});
  28.  
  29. 	while (!pq.empty())
  30. 	{
  31. 		int x = pq.top().first.first, y = pq.top().first.second;
  32. 		int dis = pq.top().second;
  33. 		pq.pop();
  34. 		if (dis != d[x][y]) continue;
  35.  
  36. 		for (int i = 0; i < 2; i++)
  37. 		{
  38. 			int x_ = x + dx[i], y_ = y + dy[i];
  39. 			if (x_ >= 1 && x_ <= n && y_ >= 1 && y_ <= m)
  40. 			{
  41. 				if (d[x_][y_] > d[x][y] + ans[a[x_][y_]])
  42. 				{
  43. 					d[x_][y_] = d[x][y] + ans[a[x_][y_]];
  44. 					pq.push({{x_, y_}, d[x_][y_]});
  45. 				}
  46. 			}
  47. 		}
  48. 	}
  49. }
  50. int main()
  51. {
  52. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  53.  
  54. 	if (fopen("CHIPHI.INP", "r"))
  55. 	{
  56. 		freopen("CHIPHI.INP", "r", stdin);
  57. 		freopen("CHIPHI.out", "w", stdout);
  58. 	}
  59.  
  60. 	int t; cin >> t;
  61. 	sieve();
  62. 	while (t--)
  63. 	{
  64. 		cin >> n >> m;
  65. 		for (int i = 1; i <= n; i++)
  66. 		{
  67. 			for (int j = 1; j <= m; j++)
  68. 			{
  69. 				cin >> a[i][j];
  70. 			}
  71. 		}
  72. 		dijkstra(1, 1);
  73. 		cout << d[n][m] << endl;
  74.  
  75. 	}
  76.  
  77. }
Success #stdin #stdout 0.01s 11572KB
comments (?)
stdin 
1
5 5
1 2 3 4 5 
1 2 3 4 5
1 2 3 4 5 
1 2 3 4 5
1 2 3 4 5
stdout 
5
https://ideone.com/tLWfaH
language:
C++14 (clang 8.0)
created:
7 hours 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!