algorithm - complexity of brute force array traversal -


if have 4x4 grid example , want start @ arbitrary cell (i,j) , want travel down every path without crossing on over myself, complexity (big o) of this? have written following code:

traverse(int[][]grid, int i, int j, boolean[][] visited){     for(int x = -1; x<=1; x++){        for(int y=-1; y<=1; y++){            if(inbounds(grid, i+x, j+y), !visited[i+x][j+y]){               traverse(grid, i+x, j+y, copyofandset(visited, i+x, j+y));            }        }     } }

assume inbounds exists , copyofandset exists , o(1) (not o(n*n)) have implemented bitwise operations clarity have used array of booleans here.

what running time of algorithm above on nxn grid.

thanks

if understand question, want enumerate self avoiding walks on 2d grid. (you said "travel down every path without crossing on over myself")

you can find several papers googling these keywords.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.5913

the problem seems #p-complete, according paper.


Comments

Post a Comment

Popular posts from this blog

c# - SharpSVN - How to get the previous revision? -

i trying find efficient way previous revision of file text comparison using sharpsvn. using (svnclient c = new svnclient()) { c.authentication.defaultcredentials = new networkcredential( configurationmanager.appsettings.get("svnserviceusername") , configurationmanager.appsettings.get("svnservicepassword") , configurationmanager.appsettings.get("svnservicedomain") ); c.authentication.sslservertrusthandlers += new eventhandler<svnsslservertrusteventargs>(authentication_sslservertrusthandlers); collection<svnfileversioneventargs> fileversioncollection = new collection<svnfileversioneventargs>(); svnrevisionrange range = new svnrevisionrange(0, this.hooks.revision); svnfileversionsargs args = new svnfileversionsargs(); args.retrieveproperties = true; args.range = range; foreach (svnchangeitem item in log.changedpaths) { string path = this.repositorypath + it...
Read more

c++ - Is it possible to compile a VST on linux? -

for class project i'm attempting write vst plugin backed cuda. current cuda workflow on linux box, i'd prefer compile , link there. according wikipedia , should possible (i couldn't find steinberg documentation relevant linux) can't find makefile or instructions on how build if aren't using xcode or visual studio. i'm vst 3 sdk doesn't support linux. when try compile plugin under linux, error: ./base/source/fatomic.cpp:39:30: fatal error: libkern/osatomic.h: no such file or directory this issue caused following code in "vst3 sdk/base/source/fatomic.cpp" #if mac #include <libkern/osatomic.h> #if mac_os_x_version_min_required > mac_os_x_version_10_4 #define native_atomic_type (volatile int32_t*) #else #define native_atomic_type (int32_t*) #endif #elif windows #include <windows.h> #endif but hope compiling under linux work vst sdk 2.4. reading. jvstwrapper seems run on lin...
Read more

url - Querystring manipulation of email Address in PHP -

i using third party application (email2http) send me emailid, body , message. unable retrieve email id due name appended on , enclosed < , >. here querystring getting. test.php?from=ajay+reddy &subject=cx&body=somebody when print variable in php returns name , not email id. $from = $_get['from']; echo $from; //output ajay reddy please suggest me how can emailid also. i dont want use post method due testing , debugging. it's working fine. forgot use htmlentities() in debugging.
Read more