Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.53 KB | None | 0 0
  1. #include<vector>
  2. #include<iostream>
  3. #include<utility>
  4. #include<chrono>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. using MATRIX = vector<vector<int>>;
  9. enum class DIRECTION {NONE,LEFT,RIGHT,UP,DOWN};
  10. static int steps=0;
  11.  
  12. void makesums(MATRIX& mat ,vector<int>& col,vector<int>& row,int n,int m)
  13. {
  14. for(int i=0;i<n;++i)
  15. {
  16. int sum=0;
  17. for(int j=0;j<m;++j)
  18. {
  19. sum+=mat[i][j];
  20. // cout<<"row "<<i<<" "<<mat[i][j]<<endl;
  21.  
  22. }
  23. col[i]=sum;
  24. }
  25. for(int i=0;i<m;++i)
  26. {
  27. int sum=0;
  28. for(int j=0;j<n;++j)
  29. {
  30. sum+=mat[j][i];
  31. //cout<<"col "<<i<<" "<<mat[j][i]<<endl;
  32.  
  33. }
  34. //cout<<"col :"<<sum<<endl;
  35. row[i]=sum;
  36. }
  37. }
  38. void move(int i,int j,MATRIX& mat ,vector<int>& col,vector<int>& row,int &n,int &m,bool l)
  39. {
  40. if(l)
  41. {
  42. row=mat[i];
  43. for(int k=0;k<n;++k)
  44. {
  45. col[k]=mat[k][j];
  46. }
  47. }
  48. row[j]-=mat[i][j];
  49. col[i]-=mat[i][j];
  50.  
  51. DIRECTION dir=DIRECTION::NONE;
  52.  
  53. /*if(!l)
  54. {
  55. for(auto elem : row)
  56. {
  57. cout<<elem<<" ";
  58. }
  59. cout<<endl;
  60. }*/
  61.  
  62.  
  63. int sumleft=0;
  64. for(int l=0;l<j;++l)
  65. {
  66. sumleft+=row[l];
  67. }
  68.  
  69. int sumright=0;
  70.  
  71. for(int r=j+1;r<m ;++r)
  72. {
  73. sumright+=row[r];
  74. }
  75.  
  76. int sumup=0;
  77. for(int u=0;u<i;++u)
  78. {
  79. sumup+=col[u];
  80. }
  81.  
  82. int sumdown=0;
  83. for(int d=i+1;d<n;++d)
  84. {
  85. sumdown+=col[d];
  86. }
  87.  
  88. vector<pair<DIRECTION,int>> pc;
  89. pc.emplace_back(DIRECTION::NONE,0);
  90. pc.emplace_back(DIRECTION::LEFT,sumleft);
  91. pc.emplace_back(DIRECTION::RIGHT,sumright);
  92. pc.emplace_back(DIRECTION::UP,sumup);
  93. pc.emplace_back(DIRECTION::DOWN,sumdown);
  94.  
  95. std::sort(pc.begin(), pc.end(), [](const std::pair<DIRECTION,int> &left, const std::pair<DIRECTION,int> &right) {
  96. return left.second < right.second;
  97. });
  98.  
  99. //cout<<"prevc"<<pc.front().second;
  100. dir=pc.front().first;
  101. /*
  102. cout<<sumleft<<endl;
  103. cout<<sumright<<endl;
  104. cout<<sumup<<endl;
  105. cout<<sumdown<<endl<<endl;
  106. */
  107.  
  108. row[i]+=mat[i][j];//sorösszegek
  109. col[j]+=mat[i][j];//oszlopösszegek
  110. switch (dir)
  111. {
  112. case DIRECTION::LEFT :
  113. //cout<<"bal"<<endl;
  114. mat[i][j]-=1;
  115. mat[i][j-1]+=1;
  116. ++steps;
  117. break;
  118. case DIRECTION::RIGHT :
  119. //cout<<"jobb"<<endl;
  120. mat[i][j]-=1;
  121. mat[i][j+1]+=1;
  122. ++steps;
  123. break;
  124. case DIRECTION::UP :
  125. //cout<<"fel"<<endl;
  126. mat[i][j]-=1;
  127. mat[i-1][j]+=1;
  128. ++steps;
  129. break;
  130. case DIRECTION::DOWN :
  131. //cout<<"le"<<endl;
  132. mat[i][j]-=1;
  133. mat[i+1][j]+=1;
  134. ++steps;
  135. break;
  136. case DIRECTION::NONE :
  137. //cout<<"NONE"<<endl;
  138. makesums(mat,col,row,n,m);
  139. move(i,j,mat, col, row,n,m,false);
  140.  
  141. break;
  142. }
  143.  
  144.  
  145. }
  146. void loop(MATRIX& mat ,vector<int>& column,vector<int>& row,int &n,int &m)
  147. {
  148. for(int i=0;i<n;++i)
  149. {
  150.  
  151. for(int j=0;j<m;++j)
  152. {
  153.  
  154. if(mat[i][j]>0)
  155. {
  156. move(i,j,mat, column, row,n,m,true);
  157. }
  158.  
  159. }
  160.  
  161. }
  162. }
  163. int main()
  164. {
  165. auto start = std::chrono::system_clock::now();
  166. int n=0;
  167. int m=0;
  168. cin>>n;
  169. cin>>m;
  170.  
  171. vector<vector<int> > mat(n);
  172. for ( int i = 0 ; i < n ; i++ )
  173. {
  174. mat[i].resize(m);
  175. }
  176. vector<int> column=vector<int>(m);
  177. vector<int> row=vector<int>(n);
  178.  
  179. for(int i=0;i<n;++i)
  180. {
  181. for(int j=0;j<m;++j)
  182. {
  183. int val = 0;
  184. cin>>val;
  185. mat[i][j]=val;
  186. }
  187. }
  188.  
  189. bool l=false;
  190. for(int k=0;k<3;++k)
  191. {
  192. loop(mat, column,row,n,m);
  193. }
  194.  
  195. for(int i=0;i<n;++i)
  196. {
  197. for(int j=0;j<m;++j)
  198. {
  199. cout<<mat[i][j]<< " ";
  200. }
  201. cout<<endl;
  202. }
  203.  
  204. cout<<steps;
  205. auto end = std::chrono::system_clock::now();
  206.  
  207. std::chrono::duration<double> elapsed_seconds = end-start;
  208. std::time_t end_time = std::chrono::system_clock::to_time_t(end);
  209.  
  210. // std::cout << "elapsed time: " << elapsed_seconds.count() <<endl;
  211.  
  212. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement