#include #include int Mezo[201][201]; bool Elo[201][201]; bool jartunk[201][201]; int P,Q; int R1, C1, R2, C2; struct pont { int x, y; pont(int a, int b) { x=a; y=b; } int mag() { return Mezo[x][y]; } bool elo() { return Elo[x][y]; } bool& be() { return jartunk[x][y]; } bool operator== (pont &b) { return x==b.x && y==b.y;} pont bal() { return pont(x-1, y); } pont jobb() { return pont(x+1, y); } pont fel() { return pont(x, y-1); } pont le() { return pont(x, y+1); } }; bool lathato( pont k, pont v) { if(k.mag() > v.mag() ) return lathato(v, k); double kmag = k.mag() + 0.5; double magkul = v.mag() - k.mag(); int dir; double dossz, dmost; if( v.x > k.x ) { dir = 1; dossz = v.x - k.x; } else if( v.x < k.x ) { dir = -1; dossz = k.x-v.x; } else goto fugg; dmost = 0.5; for(int i=k.x+dir; i!=v.x + dir; i+=dir ) { int j = int( (v.y - k.y) * (dmost+0.2777) / dossz ) + k.y; double mag = magkul*dmost/dossz + kmag; if( mag < Mezo[i][j] ) return false; dmost += 1.0; } fugg: //////////////////////////// if( v.y > k.y ) { dir = 1; dossz = v.y - k.y; } else if( v.y < k.y ) { dir = -1; dossz = k.y-v.y; } else goto vege; dmost = 0.5; for(int j=k.y+dir; j!=v.y + dir; j+=dir ) { int i = int( (v.x - k.x) * (dmost+0.2777) / dossz ) + k.x; double mag = magkul*dmost/dossz + kmag; if( mag < Mezo[i][j] ) return false; dmost += 1.0; } vege:////////// return true; } bool szomsz( pont a, pont b ) { if( b.x == 0 || b.y==0 || b.x > Q || b.y > P ) return false; if( ! b.elo() ) return false; if( b.mag() > a.mag() + 1 ) return false; if( b.mag() < a.mag() - 3) return false; return true; } void elok_szamol() { pont elso(C1,R1); pont masod(C2,R2); for(int i=1; i<=Q; i++) for(int j=1; j<=P; j++) { pont m(i,j); if( lathato(m,elso) || lathato(m, masod) ) Elo[i][j] = true; else Elo[i][j] = false; } return ; for(int j=1; j<=P; j++) { for(int i=1; i<=Q; i++) cout << Elo[i][j] << ' '; cout << endl; } cout << endl; for(int j=1; j<=P; j++) { for(int i=1; i<=Q; i++) cout << Mezo[i][j] << ' '; cout << endl; } } void kiir(int ut) { cout << "The shortest path is " << ut << " steps long.\n"; } void utat_keres() { for(int i=1; i<=Q; i++) for(int j=1; j<=P; j++ ) jartunk[i][j] = false; queue q; pont elso(C1,R1); pont utso(C2,R2); pont szt(0,0); q.push(elso); elso.be() = true; int ut = 0; while( q.size() > 0 ) { pont p = q.front(); q.pop(); if( p == szt ) { if( q.size() == 0 ) break; ut++; q.push(szt); } if( p == utso ) { kiir(ut); return; } p.be() = true; pont pp(0,0); if( szomsz(p, pp=p.bal()) ) if( szomsz(p, p.jobb()) ) if( !pp.be() ) q.push(pp); if( szomsz(p, p.fel()) ) if( !pp.be() ) q.push(pp); if( szomsz(p, p.le()) ) if( !pp.be() ) q.push(pp); } cout << "Mission impossible!\n"; } int main() { int T; cin >> T; while( T-- ) { cin >> P >> Q; for(int j=1; j<=P; j++) for(int i=1; i<=Q; i++) cin >> Mezo[i][j]; cin >> R1 >> C1 >> R2 >> C2; elok_szamol(); utat_keres(); } }