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];
- // cout<<"row "<<i<<" "<<mat[i][j]<<endl;
- }
- row[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;
- }
- column[i]=sum;
- }
- }
- void move(int i,int j,MATRIX& mat ,vector<int>& column,vector<int>& row,int n,int m)
- {
- makesums(mat,column,row,n,m);
- vector<int> actrow=row;
- vector<int> actcol=column;
- actrow[i]-=mat[i][j];//sorösszegek
- actcol[j]-=mat[i][j];//oszlopösszegek
- DIRECTION dir=DIRECTION::NONE;
- for(auto elem : actcol)
- {
- // cout<<"aaa :"<<elem<<endl;
- }
- //sorban oszlopösszegeket, oszlopban sorösszegeket kell vizsgálni
- int sumleft=0;
- for(int l=0;l<j;++l)
- {
- sumleft+=actcol[l];
- }
- if(sumleft<0)
- {
- dir=DIRECTION::LEFT;
- }
- int sumright=0;
- for(int r=j+1;r<m ;++r)
- {
- sumright+=actcol[r];
- }
- if(sumright<sumleft)
- {
- //cout<<"sumrightleft "<<sumright<<" "<<sumleft<<endl;
- dir=DIRECTION::RIGHT;
- }
- /////UPDOWN
- int sumup=0;
- for(int u=0;u<i;++u)
- {
- sumup+=actrow[u];
- }
- if(sumup<sumright && sumup<sumleft)
- {
- dir=DIRECTION::UP;
- }
- int sumdown=0;
- for(int d=i+1;d<n;++d)
- {
- sumdown+=actrow[d];
- }
- if(sumdown<sumup && sumdown<sumright && sumdown<sumleft)
- {
- dir=DIRECTION::DOWN;
- }
- ///UPDOQN
- /*
- cout<<endl;
- cout<<sumleft<<endl;
- cout<<sumright<<endl;
- cout<<sumup<<endl;
- cout<<sumdown<<endl;
- cout<<endl;
- */
- 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;
- break;
- }
- }
- int main()
- {
- auto start = std::chrono::system_clock::now();
- int n,m;
- cin>>n;
- cin>>m;
- MATRIX mat=vector<vector<int>>(n);
- vector<int> column=vector<int>(m);
- vector<int> row=vector<int>(n);
- for(int i=0;i<n;++i)
- {
- mat[i].resize(m);
- for(int j=0;j<m;++j)
- {
- int value;
- cin>>value;
- mat[i][j]=value;
- }
- }
- bool l=false;
- while(!l)
- {
- l=true;
- for(int i=0;i<n;++i)
- {
- for(int j=0;j<m;++j)
- {
- l=l&&(mat[i][j]==0);
- if(mat[i][j]>0)
- {
- move(i,j,mat, column, row,n,m);
- }
- }
- }
- }
- 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