Messages posted by: vasja

Nikola totalno se slozuvam.
Rules are rules...

Eve go moeto resenie.
Prvo pustam obicno BFS od sekoe G vo isto vreme i taka za sekoe pole go dobivam rastojanieto do najbliskiot strazar.
Potoa resenieto koristi priority_queue za da implementira nekoj vid na minimum spanning tree so Primov algoritam

)). Razlikata e toa sto tuka celo vreme go zemame poleto so najgolema vrednost namesto so najmala pa ova bi bilo "maximum spanning tree"... Mislam deka ima ista slozenost kako toa so binary search, ako ne i podobra.
Otprilika O( n * m * log(n*m) ) mislam. Ako sum greska popravete me

#include <iostream>
#include <queue>
#include <fstream>
#include <cstring>

using namespace std;

int di[]={-1,1,0,0};
int dj[]={0,0,-1,1};
char mat[1001][1001]; 
int dist[1001][1001];
bool vis[1001][1001];
vector <int> guards;
int n,m,si,sj,ei,ej;

class field
{
  public:
  field(){}
  field(int I,int J,int D) {i=I; j=J; d=D;}
  int i,j,d;
};

bool operator <(const field &a ,const field &b)
{
  return a.d<b.d;
}

void fill1()
{
  queue<int> q;
  int i,j,k;

i=0;
  memset(dist,-1,sizeof(dist));
  while(i<guards.size())
  {
    q.push(guards[i]);
    q.push(guards[i+1]);
    dist[guards[i]][guards[i+1]]=0;
    i+=2;
  }

int gi,gj;
int ni,nj;
  while(!q.empty())
  {
    gi=q.front();
    q.pop();
    gj=q.front();
    q.pop();

for(k=0;k<4;k++)
    {
      ni=gi+di[k];
      nj=gj+dj[k];

if(ni>=0 && ni<n && nj>=0 && nj<m &&  //ako e vo granici
         mat[ni][nj]!='*' && dist[ni][nj]==-1) // i ako ne e zid, i ne e poseteno
      {
         dist[ni][nj]=dist[gi][gj]+1;
         q.push(ni);
         q.push(nj);
      }
    }

}

/*
    for(i=0;i<n;i++)
    {
      for(j=0;j<m;j++)
      {
         if(dist[i][j]!=-1) cout<<" ";
         cout<<dist[i][j]<<" ";
      }
      cout<<endl;
    }
cout<<endl;
*/
}

int fill2()
{
  int res=10000000;
  priority_queue<field> q;
  memset(vis,false,sizeof(vis));
  field tmp;
  int ni,nj,k;
  q.push( field(si,sj,dist[si][sj]) );

vis[si][sj]=true;
  while(!q.empty())
  {
    tmp=q.top();
    q.pop();

if(tmp.i==ei && tmp.j==ej)
    {
      //if(tmp.d<res) res=tmp.d;
      return tmp.d;
    }

for(k=0;k<4;k++)
    {
      ni=tmp.i+di[k];
      nj=tmp.j+dj[k];
      if(ni>=0  && ni<n && nj>=0 && nj<m &&
         mat[ni][nj]!='*' && !vis[ni][nj])
      {
         q.push(field(ni,nj,min(tmp.d,dist[ni][nj])));
         vis[ni][nj]=true;
      }
    }
  }
  return res;
}

void locate()
{
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
       if(mat[i][j]=='R')
       {
            si=i; sj=j;
       }
       if(mat[i][j]=='Z')
       {
            ei=i; ej=j;
       }
       if(mat[i][j]=='G')
       {
          guards.push_back(i);
          guards.push_back(j);
       }
    }
}

int main()
{
    int i,j;

//  ifstream fin("zatvor/input/117GT_20.in");

cin>>n>>m;

for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            cin>>mat[i][j];
/*
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
          cout<<mat[i][j];
        }
        cout<<endl;
    }
*/
//cout<<"Data loading finished!\n\n";
   locate();
//cout<<"Locate() finished!\n\n";
   fill1();
//cout<<"Fill1() finished!\n\n";
   cout<<fill2();

return 0;
}

E taka e veke polesno

fala mn

Ok, fala mnogu, mene ne mi rabotea ne znam zosto...
Inaku , se nadevam ke gi postavite zadacite od regionalen za da moze lesno da gi testirame.
Fala

P.S. Imase interesni zadacki na regionalniot ( i na 2ta )

Linkot ne raboti izgleda. Proverete
Fala

Ke ja postavite prekinuvaci vo trening delot?

Mene greskata mi bese toa sto koga ke kupam vojnici pred nekoe nivo K gi upotrebuvav duri vo nivo K+1. (ne znam zosto

) Znaci ako gi kupis odma treba da gi pustis da rabotat

Otprilika mi e jasno od kodov ama ne sum siguren.
Ova e nesto kako dinamicko... Od sekoja karta imame 2 opcii , ili prevrtuvame K karti na levo ili ne prevrtuvame. Od tie 2 opcii ja zemame najmalata. Taka nekako? A povikuvas flip za 1 i 0 sto znaci probuvas da gi naprais site karti 1 ili site karti 0. Taka?
Ama sea tuka se gubam negde

plssss help

Hmm ja mozgam ja mozgam i ne mi teknuva

. Ako moze nekoj da kaze kako se resava bi vi bil mnogu blagodaren

TNX