4278 | 2023. 03. 21 15:48:41 | mraron | 2015. október | cpp17 | Elfogadva | 815ms | 32812 KiB |
//Noszály Áron 8o Debreceni Fazekas Mihály Gimnázium
#include<bits/stdc++.h>
#include<cstdlib>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
#define all(s) (s).begin(),(s).end()
#define pb push_back
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define INF std::numeric_limits<int>::max()
#define tmax(a,b,c) max((a),max((b),(c)))
#define tmin(a,b,c) min((a),min((b),(c)))
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define mp make_pair
#ifndef ONLINE_JUDGE
# define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
# define LOG(x) ((void)0)
#endif
int d2[8][2]={{1,0},{0,1},{0,-1},{-1,0},{1,1},{-1,1},{1,-1},{-1,-1}};
//---PROGRAM KEZDETE---
int d1[4][2]={{1,0},{0,1},{0,-1},{-1,0}}; //szomszédok meghatározásához
int t[805][805]; //magasságok
int h[805][805]; //szép-e ?
int n,m; //méretek
int startx, starty; //egy szép hely
bool valid(int x, int y) //egy jó koordináta, ami nem lóg ki sehol
{
return (x>=0 && y>=0 && x<n && y<m);
}
int a[805][805]; //bejárt helyek
int cnt = 0, cntmax = 0; //bejárt szép helyek, az összes szép hely
void dfs(int xx, int yy, int q) //mélységi bejárás, honnan kezdjük, legfeljebb q magasság különbség
{
stack<pair<int, int>> s;s.push(mp(xx,yy));
while(!s.empty())
{
pair<int, int> top=s.top(); s.pop();
int x=top.first, y=top.second; //mostani helyzet
if(h[x][y]==1) cnt++; //ez egy szép hely
for(int j=0;j<4;++j) //szomszédai
{
int dx = d1[j][0], dy = d1[j][1];
int xn = x+dx, yn=y+dy; //következő hely
if(valid(xn,yn) && a[xn][yn]==0 && abs(t[x][y]-t[xn][yn])<=q) //koordinátok jók és nem jártunk itt és megfelelő a magasság különbség is ideális
{
a[xn][yn]=1; //ide többé nem jövünk
s.push(mp(xn,yn)); //tovább
}
}
}
}
map<int, int> ppp;
int calc(int mid) //f(c)
{
if ( ppp.find(mid)!=ppp.end() ) return ppp[mid];
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
a[i][j]=0; //nem jártunk még sehol
}
}
a[startx][starty]=1; //dfs()-ben csak azokat 1-ezzük ki melyekbe lépünk
cnt=0;
dfs(startx, starty, mid); //mélységi bejárás
ppp[mid]=(cntmax==cnt?1:0);
return (cntmax==cnt?1:0); //ha minden szép helyet bejártunk-e?
}
int main()
{
//---BEOLVASÁS---
scanf("%d%d", &n, &m);
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
scanf("%d", &t[i][j]);
}
}
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
scanf("%d", &h[i][j]);
if(h[i][j]) //ez egy szép hely
{
cntmax++; //széphelyeink számának növelése
startx = i; starty = j;
}
}
}
//---BEOLVASÁS---
vector<int> k={0}; // az összes élszomszéd különbségének abszolút értékei (hogy ne kelljen mindig 10^9-t nézni), {0}=>hogy lekezeljük ha csak 1 és 0 szép csúcs van van
for(int i=0;i<n;++i)
{
for(int j=1;j<m;++j)
{
int val = abs(t[i][j]-t[i][j-1]);
k.pb(val);
}
}
for(int i=1;i<n;++i)
{
for(int j=0;j<m;++j)
{
int val = abs(t[i-1][j]-t[i][j]);
k.pb(val);
}
}
sort(all(k)); //rendezzük őket, hogy bináris keresést végrehajthassuk
int l=0, r=k.size()-1; //lo, up
while(l<r) //bináris keresés
{
int mid=(r+l)/2;
int midval=k[mid];
if(calc(midval)) {
r=mid;
} else {
l=mid+1;
}
}
printf("%d", k[l]);
return 0;
}
21
Elvárt kimenet:
21
Ellenőrző kimenet:
ok 1 number(s): "21"
0
Elvárt kimenet:
0
Ellenőrző kimenet:
ok 1 number(s): "0"
1
Elvárt kimenet:
1
Ellenőrző kimenet:
ok 1 number(s): "1"
21
Elvárt kimenet:
21
Ellenőrző kimenet:
ok 1 number(s): "21"
9
Elvárt kimenet:
9
Ellenőrző kimenet:
ok 1 number(s): "9"
887456
Elvárt kimenet:
887456
Ellenőrző kimenet:
ok 1 number(s): "887456"
800838205
Elvárt kimenet:
800838205
Ellenőrző kimenet:
ok 1 number(s): "800838205"
838823483
Elvárt kimenet:
838823483
Ellenőrző kimenet:
ok 1 number(s): "838823483"
779345500
Elvárt kimenet:
779345500
Ellenőrző kimenet:
ok 1 number(s): "779345500"
858627679
Elvárt kimenet:
858627679
Ellenőrző kimenet:
ok 1 number(s): "858627679"
728056287
Elvárt kimenet:
728056287
Ellenőrző kimenet:
ok 1 number(s): "728056287"
861982183
Elvárt kimenet:
861982183
Ellenőrző kimenet:
ok 1 number(s): "861982183"
723371123
Elvárt kimenet:
723371123
Ellenőrző kimenet:
ok 1 number(s): "723371123"
896373992
Elvárt kimenet:
896373992
Ellenőrző kimenet:
ok 1 number(s): "896373992"
910527745
Elvárt kimenet:
910527745
Ellenőrző kimenet:
ok 1 number(s): "910527745"
855478005
Elvárt kimenet:
855478005
Ellenőrző kimenet:
ok 1 number(s): "855478005"
904379815
Elvárt kimenet:
904379815
Ellenőrző kimenet:
ok 1 number(s): "904379815"
867165261
Elvárt kimenet:
867165261
Ellenőrző kimenet:
ok 1 number(s): "867165261"
944776036
Elvárt kimenet:
944776036
Ellenőrző kimenet:
ok 1 number(s): "944776036"
924769782
Elvárt kimenet:
924769782
Ellenőrző kimenet:
ok 1 number(s): "924769782"
850634269
Elvárt kimenet:
850634269
Ellenőrző kimenet:
ok 1 number(s): "850634269"
922216943
Elvárt kimenet:
922216943
Ellenőrző kimenet:
ok 1 number(s): "922216943"
831862676
Elvárt kimenet:
831862676
Ellenőrző kimenet:
ok 1 number(s): "831862676"
817460016
Elvárt kimenet:
817460016
Ellenőrző kimenet:
ok 1 number(s): "817460016"
931672223
Elvárt kimenet:
931672223
Ellenőrző kimenet:
ok 1 number(s): "931672223"
836673665
Elvárt kimenet:
836673665
Ellenőrző kimenet:
ok 1 number(s): "836673665"
962697444
Elvárt kimenet:
962697444
Ellenőrző kimenet:
ok 1 number(s): "962697444"