Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<vector>
- #include<iostream>
- #include<utility>
- #include<math.h>
- #include<set>
- #include<memory>
- #include<chrono>
- #include <ctime>
- using namespace std;
- using MATRIX = vector<vector<int>>;
- using P = pair<size_t,size_t>;
- using COORDINATES = multiset<pair<int,P>>;
- //set vagy multiset.
- using SEARCHRES = set<pair<P,P>>;
- enum class DIRECTION {LEFT,RIGHT,UP,DOWN,NONE};
- static int steps=0;
- void makesums(MATRIX& mat ,vector<int>& column,vector<int>& row,int n,int m)
- {
- for(int i=0;i<n;++i)
- {
- int sum=0;
- for(int j=0;j<m;++j)
- {
- sum+=mat[i][j];
- }
- row[i]=sum;
- }
- for(int i=0;i<m;++i)
- {
- int sum=0;
- for(int j=0;j<n;++j)
- {
- sum+=mat[j][i];
- }
- column[i]=sum;
- }
- }
- void move(int i,int j,MATRIX& mat ,vector<int>& column,vector<int>& row,int n,int m)
- {
- //nem biztos hogy kell a localcopy ha paraméternek jön...
- vector<int> actrow=row;
- vector<int> actcol=column;
- actrow[i]-=mat[i][j];
- actcol[j]-=mat[i][j];
- DIRECTION dir=DIRECTION::NONE;
- int sumleft=0;
- for(int l=0;l<i;++l)
- {
- sumleft+=actrow[l];
- }
- if(sumleft<0)
- {
- dir=DIRECTION::LEFT;
- }
- int sumright=0;
- for(int r=i+1;r<m ;++r)
- {
- sumright+=actrow[r];
- }
- if(sumright<sumleft)
- {
- dir=DIRECTION::RIGHT;
- }
- int sumup=0;
- for(int u=0;u<j;++u)
- {
- sumup+=actcol[u];
- }
- if(sumup<sumright)
- {
- dir=DIRECTION::UP;
- }
- int sumdown=0;
- for(int d=j+1;d<n;++d)
- {
- sumdown+=actcol[d];
- }
- if(sumdown<sumup)
- {
- dir=DIRECTION::DOWN;
- }
- /*
- cout<<endl;
- cout<<sumleft<<endl;
- cout<<sumright<<endl;
- cout<<sumup<<endl;
- cout<<sumdown<<endl;
- cout<<endl;
- */
- switch (dir)
- {
- case DIRECTION::LEFT :
- mat[i][j]-=1;
- //mat[i][j-1]+=1000;
- ++steps;
- break;
- case DIRECTION::RIGHT :
- mat[i][j]-=1;
- //mat[i][j+1]+=1000;
- ++steps;
- break;
- case DIRECTION::UP :
- mat[i][j]-=1;
- mat[i-1][j]+=1;
- ++steps;
- break;
- case DIRECTION::DOWN :
- mat[i][j]-=1;
- //mat[i][j]+=1000;
- ++steps;
- break;
- case DIRECTION::NONE :
- break;
- }
- /*
- cout<<sumleft<<endl;
- cout<<sumright<<endl;
- cout<<sumup<<endl;
- cout<<sumdown<<endl;
- cout<<endl;
- */
- }
- int main()
- {
- auto start = std::chrono::system_clock::now();
- int n,m;
- cin>>n;
- cin>>m;
- MATRIX mat=vector<vector<int>>(m);
- vector<int> column=vector<int>(n);
- vector<int> row=vector<int>(m);
- for(int i=0;i<m;++i)
- {
- mat[i].resize(n);
- for(int j=0;j<m;++j)
- {
- int value;
- cin>>value;
- mat[i][j]=value;
- }
- cout<<endl;
- }
- makesums(mat, column, row,n,m);
- for(int i=0;i<n;++i)
- {
- for(int j=0;j<m;++j)
- {
- if(mat[i][j]>0)
- {
- move(i,j,mat, column, row,n,m);
- }
- }
- }
- for(int i=0;i<n;++i)
- {
- for(int j=0;j<m;++j)
- {
- cout<<mat[i][j]<<" ";
- }
- cout<<endl;
- }
- /*
- for(int i=0;i<n;++i)
- {
- cout<<" "<<(row[i])<<endl;
- }
- cout<<endl;
- for(int i=0;i<m;++i)
- {
- cout<<(column[i])<<" ";
- }
- */
- cout<<steps;
- auto end = std::chrono::system_clock::now();
- std::chrono::duration<double> elapsed_seconds = end-start;
- std::time_t end_time = std::chrono::system_clock::to_time_t(end);
- //std::cout << "elapsed time: " << elapsed_seconds.count() <<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement