Re: Iterate over the adjacent elements in a matix container

"Alexander" <alvatov@gmail.com> wrote in message
news:3755378.2025.1317318432217.JavaMail.geo-discussion-forums@yqbr29...


I have been thinking about this algorithm and decided to write a little
example for you. It's just a quick draft but it shows what I tried to
explain to you. The helper function getAdjacents is the complex part and
this is what I have been trying to find some trick to solve. I was babbling
on a bit about using oversized arrays to solve this but I haven't though
much more about that.

I would like to say on the point about my idea looping too much that I
accept that there probably is some algorithm that can do less operations,
but most of my looping only has one simple xor condition and only satifies
this condition when it needs to.

Others have suggested other ways to do this. I can understand how an
alorithm working from the point or origin outwards could be more efficient
but I'm not sure how that would be implemented. I will think more on this.
Perhaps someone could post a short example of these other methods so we can
understand what they are talking about.

HTH
Paul.

/*****code*****/
#include <iostream>
#include<vector>

/*gets a vector of indexes adjacent to a given index*/
std::vector<int> getAdjacents(int index, int rows=7, int cols=8){
 std::vector<int> ret;
 if( (index/cols==(index-1)/cols)&& index!=0 ) ret.push_back(index-1);
 if((index+1)%cols) ret.push_back(index+1);
 if(index-cols>=0) ret.push_back(index-cols);
 if( (index+cols)<(rows*cols)) ret.push_back(index+cols);
 return ret;
}

/*parameter 'clicked' represents the index of the tile that was clicked*/
void clickme(std::vector<int>& v, int clicked=15, int newval=4){
 std::vector<bool> b1(v.size(),0);
 std::vector<bool> b2(v.size(),0);
 std::vector<int> adjacents;
 int initval= v[clicked];
 v[clicked]=newval;
 b2[clicked]=1;
 /*b2 represents all tiles whos value has been changed*/
 /*b1 represents all tiles whos adjacents have been checked*/

 /*loop to find a tile whos value has been changed but its adjacents have
not not been checked*/
 for(int i=0; i<b1.size(); ++i){
  if(b1[i]^b2[i]){
   /*ok found one, check its adjacents*/
   adjacents = getAdjacents(i);
   /*inner loop will loop 2-4 times only*/
   for(int j=0; j<adjacents.size(); ++j){
    if(v[adjacents[j]]== initval){
     v[adjacents[j]]=newval;
     b2[adjacents[j]]=1;
    }
   }
   /*mark this tile as having had its adjacents checked*/
   b1[i]=1;
   /*reset loop and find another tile whos value has been changed*/
   i=0;
   adjacents.clear();
  }
 }
}

int main(){
 /*Example vector to repsresent a 7x8 matrix*/
 std::vector<int> v(56,2);
 v[5]=3;
 v[13]=3;
 v[21]=3;
 v[22]=3;
 v[23]=3;
 std::cout<<"Before clickme:";
 for(int i=0; i<v.size(); ++i){
  if(i%8==0) std::cout<<std::endl;
  std::cout<< v[i];
 }
 clickme(v);
 std::cout<<"\n\nAfter clickme:";
 for(int i=0; i<v.size(); ++i){
  if(i%8==0) std::cout<<std::endl;
  std::cout<< v[i];
 }
}

/*It's a bit rough and definately not unbreakable but its just an example*/

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---