http://mendo.mk/jforum/posts/list/6.page JForum - http://www.jforum.net #include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int R, C;
bool WithinRange(int x, int y)
{
if((x>=0 && x<R) && (y>=0 && y<C))
return true;
return false;
}
int main()
{
int number_years;
cin>>number_years;
vector<int> years;
for(int i=0;i<number_years;i++)
{
int year;
cin>>year;
years.push_back(year);
}
cin>>R>>C;
int MAT[R][C];
for(int i=0;i<R;i++)
{
for(int j=0;j<C;j++)
{
cin>>MAT[i][j];
}
}
queue<pair<int, int> >q;
bool VIS[R][C];
memset(VIS,false,sizeof(VIS));
int delta_x[]={1,0,-1,0};
int delta_y[]={0,1,0,-1};
vector<int> ekspo;

for(int i=0;i<number_years;i++)
{
vector<pair<int,int> > cords;
memset(VIS,false,sizeof(VIS));
for(int j=0;j<R;j++)
{
for(int k=0;k<C;k++)
{
if(years[i]>=MAT[j][k])
VIS[j][k]=true;
else
cords.push_back(make_pair(j,k));
}
}
int eks=0;
for(int i=0;i<cords.size();i++)
{
pair<int, int> at1=cords[i];
if(VIS[at1.first][at1.second]==false)
{
eks++;
q.push(at1);
while(!q.empty())
{
pair<int, int> at=q.front();
q.pop();
for(int dir=0;dir<4;dir++)
{
int x=at.first, y=at.second;
int next_x=x+delta_x[dir], next_y=y+delta_y[dir];
if(WithinRange(next_x,next_y)==true && VIS[next_x][next_y]==false )
{
q.push(make_pair(next_x, next_y));
VIS[next_x][next_y]=true;
}
}
}
}
}
ekspo.push_back(eks);
}
for(int i=0;i<ekspo.size();i++)
cout<<ekspo[i]<<endl;
}
[/code]
Овој код ми дава 8/20 точни тест примери останатите 12 ми паѓаат на време, може помош!!
]]> http://mendo.mk/jforum/posts/preList/666/3659.page http://mendo.mk/jforum/posts/preList/666/3659.page GMT Пред да почнеш со решавање, треба да си направиш анализа на временската сложеност на решението, за да знаеш дали ќе помине на време уште пред да почнеш со куцање на кодот (освен ако не можеш да дојдеш до соодветно решение - тогаш може и вакво, бидејќи ќе освои и ова неколку поени на натпревар или испит или на што и да е).

За задачава, 1) пробај годините да ги гледаш во обратен редослед, 2) види го ова предавање http://mendo.mk/Lecture.do?id=44 и размисли како може да примениме union-find во задачата.]]> http://mendo.mk/jforum/posts/preList/666/3662.page http://mendo.mk/jforum/posts/preList/666/3662.page GMT