Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<vector>
- #include<iostream>
- #include<utility>
- #include<chrono>
- #include <algorithm>
- using namespace std;
- using MATRIX = vector<vector<int>>;
- enum class DIRECTION {NONE,LEFT,RIGHT,UP,DOWN};
- static int steps=0;
- void makesums(MATRIX& mat ,vector<int>& col,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];
- // cout<<"row "<<i<<" "<<mat[i][j]<<endl;
- }
- col[i]=sum;
- }
- for(int i=0;i<m;++i)
- {
- int sum=0;
- for(int j=0;j<n;++j)
- {
- sum+=mat[j][i];
- //cout<<"col "<<i<<" "<<mat[j][i]<<endl;
- }
- //cout<<"col :"<<sum<<endl;
- row[i]=sum;
- }
- }
- void move(int i,int j,MATRIX& mat ,vector<int>& col,vector<int>& row,int &n,int &m,bool l)
- {
- if(l)
- {
- row=mat[i];
- for(int k=0;k<n;++k)
- {
- col[k]=mat[k][j];
- }
- }
- row[j]-=mat[i][j];
- col[i]-=mat[i][j];
- DIRECTION dir=DIRECTION::NONE;
- /*if(!l)
- {
- for(auto elem : row)
- {
- cout<<elem<<" ";
- }
- cout<<endl;
- }*/
- int sumleft=0;
- for(int l=0;l<j;++l)
- {
- sumleft+=row[l];
- }
- int sumright=0;
- for(int r=j+1;r<m ;++r)
- {
- sumright+=row[r];
- }
- int sumup=0;
- for(int u=0;u<i;++u)
- {
- sumup+=col[u];
- }
- int sumdown=0;
- for(int d=i+1;d<n;++d)
- {
- sumdown+=col[d];
- }
- vector<pair<DIRECTION,int>> pc;
- pc.emplace_back(DIRECTION::NONE,0);
- pc.emplace_back(DIRECTION::LEFT,sumleft);
- pc.emplace_back(DIRECTION::RIGHT,sumright);
- pc.emplace_back(DIRECTION::UP,sumup);
- pc.emplace_back(DIRECTION::DOWN,sumdown);
- std::sort(pc.begin(), pc.end(), [](const std::pair<DIRECTION,int> &left, const std::pair<DIRECTION,int> &right) {
- return left.second < right.second;
- });
- //cout<<"prevc"<<pc.front().second;
- dir=pc.front().first;
- /*
- cout<<sumleft<<endl;
- cout<<sumright<<endl;
- cout<<sumup<<endl;
- cout<<sumdown<<endl<<endl;
- */
- row[i]+=mat[i][j];//sorösszegek
- col[j]+=mat[i][j];//oszlopösszegek
- switch (dir)
- {
- case DIRECTION::LEFT :
- //cout<<"bal"<<endl;
- mat[i][j]-=1;
- mat[i][j-1]+=1;
- ++steps;
- break;
- case DIRECTION::RIGHT :
- //cout<<"jobb"<<endl;
- mat[i][j]-=1;
- mat[i][j+1]+=1;
- ++steps;
- break;
- case DIRECTION::UP :
- //cout<<"fel"<<endl;
- mat[i][j]-=1;
- mat[i-1][j]+=1;
- ++steps;
- break;
- case DIRECTION::DOWN :
- //cout<<"le"<<endl;
- mat[i][j]-=1;
- mat[i+1][j]+=1;
- ++steps;
- break;
- case DIRECTION::NONE :
- //cout<<"NONE"<<endl;
- makesums(mat,col,row,n,m);
- move(i,j,mat, col, row,n,m,false);
- break;
- }
- }
- void loop(MATRIX& mat ,vector<int>& column,vector<int>& row,int &n,int &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,true);
- }
- }
- }
- }
- int main()
- {
- auto start = std::chrono::system_clock::now();
- int n=0;
- int m=0;
- cin>>n;
- cin>>m;
- vector<vector<int> > mat(n);
- for ( int i = 0 ; i < n ; i++ )
- {
- mat[i].resize(m);
- }
- vector<int> column=vector<int>(m);
- vector<int> row=vector<int>(n);
- for(int i=0;i<n;++i)
- {
- for(int j=0;j<m;++j)
- {
- int val = 0;
- cin>>val;
- mat[i][j]=val;
- }
- }
- bool l=false;
- for(int k=0;k<3;++k)
- {
- loop(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;
- }
- 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