// // main.cpp // model e // // Created by Nasca Sergiu Alin on 12/02/16. // Copyright © 2016 Nasca Sergiu Alin. All rights reserved. // #include #include #include #define INF 1<<30 typedef struct { int x,y; }Punct; int a[201][201],b[201][201]; std::queue coada; int dx[] = {0,1,0,-1}; int dy[] = {1,0,-1,0}; void createMatrixTest() { int lin,col; for( int i = 0; i < 200; ++i) { for( int j = 0; j < 200; ++j)b[i][j] = INF; } coada.push({ 1, 0 }); b[1][0] = 0; while(!coada.empty()) { lin = coada.front().x; col = coada.front().y; coada.pop(); for( int k = 0; k <= 3; ++k) { if( col + dy[k] >= 0 && col + dy[k] < 200 && lin + dx[k] >= 0 && lin + dx[k] < 200 && b[lin + dx[k]][col + dy[k]] == INF ) { if( k < 2)b[lin + dx[k]][col + dy[k]] = b[lin][col] + 1; else b[lin + dx[k]][col + dy[k]] = b[lin][col] - 1; coada.push({ lin + dx[k], col + dy[k] }); } } } for( int i = 0; i < 200; ++i) { for( int j = 0; j < 200; ++j)printf("%d ",b[i][j]); printf("\n"); } } int returnTestNumber(int lin,int col) { return b[lin][col]; } void flushBuffer() { std::cout<<"\n"; std::cout.flush(); } void finded(int x) { printf(" %d\n",x); if(x == 0)exit(0); } bool comparePoints(Punct A,Punct B) { if(A.x == B.x && A.y == B.y)return true; return false; } bool signPoints(Punct A, Punct B) { if( a[A.x][A.y] * a[B.x][B.y] >= 0 )return true; return false; } bool validPoint(Punct A) { if(A.x < 0 || A.y < 0)return false; if(a[A.x][A.y] != INF)return false; return true; } Punct binarysearch(Punct A, Punct B) { Punct mij; while(true) { mij.x = (A.x + B.x)/2; mij.y = (A.y + B.y)/2; if(comparePoints(mij, A) || comparePoints(mij, B))break; std::cout<>a[mij.x][mij.y]; //a[mij.x][mij.y] = returnTestNumber(mij.x, mij.y); if(signPoints(mij, A))A = mij; else B = mij; } return B; } void divImpera(Punct A,Punct B) { if(!validPoint(A) || !validPoint(B))return; std::cout<>a[A.x][A.y]; //a[A.x][A.y] = returnTestNumber(A.x, A.y); //finded(a[A.x][A.y]); std::cout<>a[B.x][B.y]; //a[B.x][B.y] = returnTestNumber(B.x, B.y); //finded(a[B.x][B.y]); Punct mij = binarysearch(A, B); divImpera({A.x,mij.y}, {mij.x-1,B.y}); divImpera({mij.x,A.y}, {B.x,mij.y-1}); } int main() { for(int i=0;i<200;++i) { for(int j=0;j<200;++j)a[i][j] = INF; } //createMatrixTest(); divImpera({0,0}, {199,199}); return 0; }