Advertisement
Guest User

Untitled

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