Doggy 的狗窝

文章数零，光凭着一个标题都能上3万的访问量。faint2003次until death。

若干年后，我们会说：方兴东靠的是木子美，水木靠的是冰火可儿。

决赛在日本，比去年增加了不少项目。
Algorithm：和去年一样，连题目都没怎么变，奖金增加了。
Visual Gaming：编写bots的AI，根电脑斗，与人斗。这个最有意思了。

详情见
http://imagine.thespoke.edu.cn/
报名
http://imagine.thespoke.net

另外出售去年考题，呵呵。

zz from thespoke

I dont have the exact subject, so I’ll try to give as many information as I can
There were 3 binary problems:

1) SMS decoder
You have a code (I dont remember it, but it is something like 1 stands for a, 11 for b, 12 for c, 2 for d… even if it is called SMS decoder, I’m not sure it was SMS), a dictionary, and a text to decode.
There is a code for ‘-’, and a word formed with two words in the dictionary separated by - is correct…

2) 8 puzzle (taquin in french, nobody managed to give me the english name)
You have a 3*3 puzzle filled with 8 pieces (numbered from 1 to and a hole. You can move one of the 4 pieces around the hole toward the hole (hard to explain, but easy to play ;))
Given a starting position, your program must output the differents steps to get to the solution where the pieces are ordered.

3) Crossword solver
You are given an empty crossword grid (the black cells are already placed) and a list of words. You have to fill the grid with the words

There were 4 optimization problems:

1) Image compression
You were given 15 image of the same thing (from different angles) (a beach: blue sky, yellow sand :)), and will have to compress the 16th

2) Fingerprint recognition
You are given the bitmap images of 9 fingerprints of 17 people (in 256 grey level). The judges have the 10th one, will input it to your algorithm. It must say whose fingerprint it is

3) Traveling salesman problem
You have a car that runs at 1000km/h (nice car isnt it ?), can do 20km with 1L of gaz, and can be filled with 50L of gaz.
There is 5000 hide outs on a map with coordinates from (-500, -500) to (500, 500). You have 72h to go through as many hideouts as possible starting and ending at (0, 0).
In 1000 of the 5000 hideouts, you can fill up your car with gaz

4) Spy world
This game is quite complex: it is played on a 30 * 30 board, you have some pieces (that looks like tetris one (but are made of only 5 squares)). Each player play and place a piece on the board.
Depending on the shape of the piece, their role is different (on is a command center, one is a communication center, one represents a civilian and one is a bunker).
You get some points by placing a communication center near an ennemy command center that has no bunker around him, or by placing some linked command centers (meaning that a path exists from one command center to the other by moving only on your pieces).

 

a few words about the solution ChauJY posted 
Since it turns out the contest had little to do with good algorithms, only with fast code, I want to take a look at the solution ChauJY posted, because it can easily be used as a tutorial on how not to write fast code.

I think almost every mistake that could be made was made in this code. Let me try to list a few key points:

1. strings: this is the one that hurt the most, since the constructor was the only place that had a significant amount of work to do. To put it simple, you should never use strings in fast code. Especially the managed ones that are non-mutable and in every operation allocate memory, copy, and create work for the garbage collector. A ReadLine() alone is enough to make the code very slow; the Split() makes things drastically worse, creating an extra array and two strings in the heap. I hope everybody knows memory allocation is veeeery slow: well, you have to think about the implicit memory allocations as well. This is what causes the problems, I’m sure Parse() is not much slower than myatoi(). This is even more important for Problem 2!

2. branches: never leave a branch that can be avoided. Especially unpredictable ones, such as the r[e1] == 0 tests in the main function. It is so easy to remove this test, you just need to add (1-r[e1]) to p1. Setting s1[p1] does not need to be conditional (with a little shuffling of the code). An incorrectly predicted branch costs quite a few cycles on modern machines and is going to cost even more on future architectures.

3. structure of arrays vs. array of structures: since every time you’re using m[i] you also need r[i], think about what happens when you need data that is not in the L1 cache: the system has to load the cache line that contains m[i] and then it has to load another cache line for r[i]. If you use an array of structures, every time you load s[i].m, s[i].r resides in the same cache line and comes with it to the L1 cache for free. No second load is needed. The gain is quite substantial even for transfers from L2 cache. Also, if you need to use a structure of arrays, avoid power-of-two lengths. They cause cache associativity problems.

4. packing indices: try to keep the data as densely packed as possible. In other words, you do not need an array of 100000 elements for the m and r arrays. You can use a 100000-element map that guarantees the indices you’re actually working with remain packed in the beginning of the 0 to 29999 range. This also lets you use 16-bit ints as indices, the data can more easily fit the caches, and there is a greater chance that a cache line load will carry useable extra information. (btw. the code gives wrong results because it’s using short ints without taking care to put the indices in the correct range)

5. benchmarking: do it after every significant change. You can’t know every factor that affects the performance, so an idea that looks good might prove counterproductive. If you benchmark, you’ll see this at once.

All of this (and more) is present in my code. I’m not saying my solution to this problem is a good algorithm, I don’t like it myself. But you could easily improve yours by looking at a few things I’ve done there, although many of my optimizations are counterproductive with the actual data sets just because my code is longer than it could be. 

下载了牛人Branimir_Lambov（前5名之一）的程序，这是他的时间：

0.0415455039474182
ConstructorTime: 0.02962276
GetDegreesOfSeperation time (Called 100 times): 0.008900293
RemoveEmployee time (Called 10 times): 0.000840889
GetDegreesOfSeperation time (Called 100 times): 0.002181562

这是我的时间：

0.157306305743987
ConstructorTime: 0.1524725
GetDegreesOfSeperation time (Called 100 times): 0.004037943
RemoveEmployee time (Called 10 times): 0.0005053715
GetDegreesOfSeperation time (Called 100 times): 0.0002905397

看了一下程序，发现读文件有很大区别。他自己做了一个简单的atoi函数，使用Read()一个一个字符读，而我用的是ReadLine()和Parse()。稍微修改了一下我的程序，拷贝了他的myatoi()函数，代替了ReadLine()和Parse()。时间变成：

0.0293408803408965
ConstructorTime: 0.02604102
GetDegreesOfSeperation time (Called 100 times): 0.002481041
RemoveEmployee time (Called 10 times): 0.0005341461
GetDegreesOfSeperation time (Called 100 times): 0.0002846731

靠，简直是第一名的速度了！呵呵，不过这个测试数据有问题，求的距离很少，对复杂算法不利。Branimir_Lambov使用的就是<O(n), O(1)>算法。下面是程序修改部分。

  // quick and ugly atoi
  int myatoi(StreamReader s)
  {
   int c = s.Read();
   if (c==’-')
   {
    s.Read();
    s.Read();
    return -1;
   }
   if(c==’\r’||c==-1)
    return -5;
   int v = c - ‘0′;
   c = s.Read();
   while (c >= ‘0′ && c <= ‘9′)
   {
    v = v*10 + c - ‘0′;
    c = s.Read();
   }
   return v;
  }

  public Company(string hierarchyFile)
  {
   // ———- read file ———-0.0015
   StreamReader infile = new StreamReader(hierarchyFile);
   short ee=1, mg=2;
   while(true)
   {
    ee = (short)myatoi(infile); // this will also get the ‘\t’
    if(ee==-5)
     break;
    mg = (short)myatoi(infile); // this will get the ‘\r’
    m[ee] = mg;
    int c = infile.Read(); // this gets the ‘\n’
    if(c==-1)
     break;
   }
   infile.Close(); // 0.05ms
   return;
  }

接着是Branimir_Lambov的程序(C++):

#pragma once
#using <mscorlib.dll>

#ifdef _DEBUG
 #include <assert.h>
#else
 #undef assert
 #define assert(x)
#endif

using namespace System;
using namespace System::IO;

namespace ImagineCup
{
 const int FULLSIZE = 30001;
 const int MAPSIZE = 100001;
 typedef short unsigned int VIZINT;
 typedef unsigned int VISINT;
 typedef signed int PTRINT;
 typedef short signed int PTZINT;

 // the algorithm is simple: to find the degrees of separation (DOS), just go
 // up the hieriarchy as fast as you can on both sides, marking every spot
 // you’ve been to and adding an employee’s "Alive" value every time you run
 // through one. finding a spot already visited by the other side means you’re
 // done. the code is heavily unrolled to save 3 out of 4 conditional branches.

 // removing is done by simply setting the "Alive" value to 0. We’re also setting the
 // "jump" value to the difference between the employee’s index and its manager’s.
 // to make things faster, the number of removed employees is counted, and 1/8
 // of this number of the following degrees of separation calls add the manager’s
 // jump value to the manager index of every employee they pass through. The rest of
 // the calls are done with the same algorithm as in the previous paragraph.

 public __gc class Company
 {
 public:
  #define STRUCPAD 4  // to accommodate -1 to -4 which are needed as buffer for
  #define TOP -STRUCPAD // the quick search, so that setting VLevel of the TOP
        // does not occur because we’re looping

  //PTZINT indexmap __nogc [MAPSIZE+STRUCPAD];
  PTZINT indexmap __gc [];
  __value struct DataStruc {
   PTZINT mgr;
   PTZINT jump;
   VIZINT alive;
   VIZINT vlev;
   VIZINT vis1;
   VIZINT vis2;
  };
#ifndef REALLY_BAD_JUDGES
  DataStruc data __nogc [FULLSIZE+STRUCPAD];
#else
  DataStruc data __gc [];
#endif

#define Manager(i) data[i+STRUCPAD].mgr  // the employee’s manager
#define Alive(i) data[i+STRUCPAD].alive  // 1 if the employee has not been removed
#define Visited1(i) data[i+STRUCPAD].vis1 // set to a call index when we pass through this employee
#define Visited2(i) data[i+STRUCPAD].vis2 // set to a call index when we pass through this employee
#define VLevel(i) data[i+STRUCPAD].vlev  // the DOS at which we visited this spot
#define Jump(i) data[i+STRUCPAD].jump  // 0 if the employee is alive, ow. the difference between its index and the manager’s.
           // saves a comparison at the expense of an addition

#define Map(i) indexmap[i+STRUCPAD]   // the employee’s IDs are mapped to low indices to maximize locality of the data
           // and to be able to use short ints for indices

  int anythingdeleted;    // how many employees have been removed
  int dcall;       // call number after employees have been removed

  Company(String* hierarchyFile);

  int GetDegreesOfSeparation(int employeeID_1, int employeeID_2);
  void RemoveEmployee(int employeeID);

  // slow method, used to test
  int CrawlDegreesOfSeparation(PTRINT employeeID_1, PTRINT employeeID_2, VISINT call);

  // method that applies the jumps– no fast counterpart possible
  int CrawlDegreesOfSeparationJump(PTRINT employeeID_1, PTRINT employeeID_2, VISINT call);

  // unrolled method
  int DOSUnrolled(PTRINT employeeID_1, PTRINT employeeID_2, VISINT call);
 };

#ifdef _DEBUG
 // I used this to generate some test cases
 void GenerateRandom()
 {
  int num = 0;

  StreamWriter *fo = new StreamWriter("Problem1_Hierarchy.txt");
  int man = -1;
  fo->WriteLine("{0}\t{1}", __box(num), __box(man));
  ++num;
  Random *r = new Random;
  while (num < 30000) {
   double dbl = r->NextDouble();
   // get closer to the newer members
   dbl *= dbl;
   dbl *= dbl;
   dbl *= dbl;
   dbl *= dbl;
   man = num -1 - int(dbl*num);
   fo->WriteLine("{0}\t{1}", __box(num), __box(man));
   ++num;
  }
  fo->Close();
  int i;

  int rmv[FULLSIZE];
  StreamWriter *f1 = new StreamWriter("Problem1_Relationships1.txt");
  StreamWriter *f2 = new StreamWriter("Problem1_Relationships2.txt");
  StreamWriter *fr = new StreamWriter("Problem1_Removelist.txt");
  for (i = 0; i<20000; ++i) {
   f1->WriteLine("{0}\t{1}", __box(r->Next(num)), __box(r->Next(num)));
  }
  f1->Close();
  for (i = 0; i<20000; ++i) {
   int v = r->Next(num);
   // don’t remove twice
   if (!rmv[v]) {
    fr->WriteLine("{0}", __box(v));
    rmv[v] = 1;
   }
  }
  fr->Close();
  for (i = 0; i<60000; ++i) {
   int v1 = r->Next(num);
   int v2 = r->Next(num);
   // no relationship queries between removed
   if (!rmv[v1] && !rmv[v2])
    f2->WriteLine("{0}\t{1}", __box(v1), __box(v2));
  }
  f2->Close();
 }
#endif

 // quick and ugly atoi
 int myatoi(StreamReader *s)
 {
  int c = s->Read();
  if (c==’-') {
   s->Read();
   s->Read();
   return -1;
  }
  int v = c - ‘0′;
  c = s->Read();
  while (c >= ‘0′ && c <= ‘9′) {
   v = v*10 + c - ‘0′;
   c = s->Read();
  }
  return v;
 }
 
 Company::Company(String* hierarchyFile)
 {
  int i;
  //GenerateRandom();
  dcall = 0;
  int mapcnt = 1;
  indexmap = new PTZINT __gc[MAPSIZE+STRUCPAD];
#ifdef REALLY_BAD_JUDGES
  data = new DataStruc __gc [FULLSIZE+STRUCPAD];
#endif

  for (i=TOP;i<0;++i) {
   Manager(i) = i-1;
  }
  Manager(TOP) = TOP;
  StreamReader *f = new StreamReader(hierarchyFile);
  anythingdeleted = 0;
  Map(-1) = -1;

  int e, m;
  while (f->Peek()!=-1) {
   e = myatoi(f); // this will also get the ‘\t’
   m = myatoi(f); // this will get the ‘\r’
   char c = f->Read(); // this gets the ‘\n’
   assert(c == ‘\n’);
   if (!Map(e)) Map(e) = mapcnt++;
   e = Map(e);
   if (!Map(m)) Map(m) = mapcnt++;
   m = Map(m);
   Manager(e) = m;
   Alive(e) = 1;
  }
  f->Close();
 }

 int Company::CrawlDegreesOfSeparation(PTRINT e1, PTRINT e2, VISINT call)
 {
  VISINT lev1 = 0;
  VISINT lev2 = 0;

  // we use Visited == call to signal that we’ve visited a point.
  // this way we save costly initialization
  // GetDegreesOfSeparation makes sure this is false when these functions are called

  Visited1(e1) = call;
  VLevel(e1) = lev1;
  while (1) {
   lev1 += Alive(e1);
   Visited2(e2) = call;
   VLevel(e2) = lev2;
   lev2 += Alive(e2);

   e1 = Manager(e1);
   e2 = Manager(e2);

   if (Visited2(e1)==call) {
    return VLevel(e1) + lev1 - 1;
   }
   Visited1(e1) = call;
   VLevel(e1) = lev1;

   if (Visited1(e2)==call) {
    return VLevel(e2) + lev2 - 1;
   }
   
  };

  return -1;
 }

 // this one updates the managers to make next calls faster
 int Company::CrawlDegreesOfSeparationJump(PTRINT e1, PTRINT e2, VISINT call)
 {
  VISINT lev1 = 0;
  VISINT lev2 = 0;
  PTRINT m1, m2;

  Visited1(e1) = call;
  VLevel(e1) = lev1;
  while (1) {
   lev1 += Alive(e1);
   Visited2(e2) = call;
   VLevel(e2) = lev2;
   lev2 += Alive(e2);

   m1 = Manager(e1);
   m2 = Manager(e2);
   Manager(e1)=m1+Jump(m1);
   Manager(e2)=m2+Jump(m2);
   e1 = m1;
   e2 = m2;

   if (Visited2(e1)==call) {
    return VLevel(e1) + lev1 - 1;
   }
   Visited1(e1) = call;
   VLevel(e1) = lev1;

   if (Visited1(e2)==call) {
    return VLevel(e2) + lev2 - 1;
   }
   
  };

  return -1;
 }

 // the fast function
 int Company::DOSUnrolled(PTRINT e1, PTRINT e2, VISINT call)
 {
  VISINT lev1 = 0;
  VISINT lev2 = 0;

  PTRINT oe1;
  PTRINT oe2;

  Visited1(TOP) = call;  // to save a conditional branch in the loop
  Visited2(TOP) = call;

  Visited1(e1) = call;
  VLevel(e1) = lev1;
  while (1) {
   oe1 = e1;
   oe2 = e2;

   // unrolled code, if’s only after 4 climbs
   lev1 += Alive(e1);
   Visited2(e2) = call;
   VLevel(e2) = lev2;
   lev2 += Alive(e2);

   e1 = Manager(e1);
   e2 = Manager(e2);

   Visited1(e1) = call;
   VLevel(e1) = lev1;

   lev1 += Alive(e1);
   Visited2(e2) = call;
   VLevel(e2) = lev2;
   lev2 += Alive(e2);

   e1 = Manager(e1);
   e2 = Manager(e2);

   Visited1(e1) = call;
   VLevel(e1) = lev1;

   lev1 += Alive(e1);
   Visited2(e2) = call;
   VLevel(e2) = lev2;
   lev2 += Alive(e2);

   e1 = Manager(e1);
   e2 = Manager(e2);

   Visited1(e1) = call;
   VLevel(e1) = lev1;

   lev1 += Alive(e1);
   Visited2(e2) = call;
   VLevel(e2) = lev2;
   lev2 += Alive(e2);

   e1 = Manager(e1);
   e2 = Manager(e2);

   if (Visited2(e1)==call) {
    // oops now we gotta check when that actually happened,
    // and whether it isn’t that we’ve simply reached the TOP

    if (e1 == TOP) {
     // if we’ve reached the top, first check if
     // we’ve not entered the wrong loop exit, i.e.
     // if the e2 climb is not just finished
     if (Visited1(e2)!=call) break;
     else {
      VISINT vl = VLevel(e2);
      VLevel(e2) = lev2;
      while (Visited1(oe2)!=call) {
       oe2 = Manager(oe2);
      }
      VISINT ile2 = lev2 - VLevel(oe2);
      return vl + lev2 - 1 - 2*ile2;
     }
    }

    VISINT vl = VLevel(e1);
    VLevel(e1) = lev1;

    while (Visited2(oe1)!=call) {
     oe1 = Manager(oe1);
    }

    VISINT ile1 = lev1 - VLevel(oe1);
    return vl + lev1 - 1 - 2*ile1;
   }
   Visited1(e1) = call;
   VLevel(e1) = lev1;
   if (Visited1(e2)==call) {
    if (e2 == TOP) {
     assert(Visited2(e1)!=call);
     break;
    }
    VISINT vl = VLevel(e2);
    VLevel(e2) = lev2;
    while (Visited1(oe2)!=call) {
     oe2 = Manager(oe2);
    }
    VISINT ile2 = lev2 - VLevel(oe2);
    return vl + lev2 - 1 - 2*ile2;
   }
   // this would be the place to check for (e1==TOP || e2==TOP)
   // if we didn’t set TOP’s visited values
  }

  // finish off working only on one of the sides
  if (e1 < 0) {
   while (1) {
    oe2 = e2;

    // unrolled code, if’s only after 4 climbs
    Visited2(e2) = call;
    VLevel(e2) = lev2;
    lev2 += Alive(e2);
    e2 = Manager(e2);

    Visited2(e2) = call;
    VLevel(e2) = lev2;
    lev2 += Alive(e2);
    e2 = Manager(e2);

    Visited2(e2) = call;
    VLevel(e2) = lev2;
    lev2 += Alive(e2);
    e2 = Manager(e2);

    Visited2(e2) = call;
    VLevel(e2) = lev2;
    lev2 += Alive(e2);
    e2 = Manager(e2);

    if (Visited1(e2)==call) {
     VISINT vl = VLevel(e2);
     VLevel(e2) = lev2;
     while (Visited1(oe2)!=call) {
      oe2 = Manager(oe2);
     }
     VISINT ile2 = lev2 - VLevel(oe2);
     return vl + lev2 - 1 - 2*ile2;
    }
    
   }
  } else { // e2 < 0
   while (1) {
    oe1 = e1;

    // unrolled code, if’s only after 4 climbs
    lev1 += Alive(e1);
    e1 = Manager(e1);

    Visited1(e1) = call;
    VLevel(e1) = lev1;

    lev1 += Alive(e1);
    e1 = Manager(e1);

    Visited1(e1) = call;
    VLevel(e1) = lev1;

    lev1 += Alive(e1);
    e1 = Manager(e1);

    Visited1(e1) = call;
    VLevel(e1) = lev1;

    lev1 += Alive(e1);
    e1 = Manager(e1);

    if (Visited2(e1)==call) {
     // oops now we gotta check when that actually happened
     VISINT vl = VLevel(e1);
     VLevel(e1) = lev1;
     while (Visited2(oe1)!=call) {
      oe1 = Manager(oe1);
     }
     VISINT ile1 = lev1 - VLevel(oe1);
     return vl + lev1 - 1 - 2*ile1;
    }
    Visited1(e1) = call;
    VLevel(e1) = lev1;

   }
  }

  return -1;
 }

 int Company::GetDegreesOfSeparation(int e1, int e2)
 {
  static VIZINT call = 1;
  if (e1 == e2) return 0;
  e1 = Map(e1); e2 = Map(e2);
  assert(e1 && e2);
  if (++call==0) { // if call wraps, we have to clean all Visited values
   for (int i=TOP;i<FULLSIZE;++i)
    Visited1(i) = Visited2(i) = 0;
   call+=2;
  };

  int r;
  #ifdef _DEBUG
  int v = CrawlDegreesOfSeparation(e1, e2, call++);
  #endif

  if (anythingdeleted) {
   if (dcall<(anythingdeleted*1/8)) {
    ++dcall;
    r = CrawlDegreesOfSeparationJump(e1, e2, call);
   } else
    r = DOSUnrolled(e1, e2, call);
  } else
   r = DOSUnrolled(e1, e2, call);

  #ifdef _DEBUG  
  if (v!=r) {
   Console::WriteLine("Quick {0}, Crawl {1}, e1 {2}, e2 {3}", __box(r), __box(v), __box(e1), __box(e2));
  }
  #endif

  return r;
 }

 void Company::RemoveEmployee(int employeeID)
 {
  employeeID = Map(employeeID);
  assert(employeeID);

#ifdef _DEBUG
  if (!anythingdeleted) Console::WriteLine("Removing people…");
#endif
  Alive(employeeID) = 0;
  Jump(employeeID) = Manager(employeeID) - employeeID;
  ++anythingdeleted;

 }
}

Final Rank

32

 

 

P1 Rank	P1.1 %	P1.2 %	P1.3 %
60	n/a%	n/a%	n/a%

第一题居然没有成绩，给我算的最后一名60。靠，虽然就算这题名次再好我也不能参加决赛了，不过还是很不爽。

P2 Rank	P2.1 %	P2.2 %	P2.3 %
24	597%	727%	806%

 

P3 Rank	P3.1 %	P3.2 %	P3.3 %
27	461%	495%	440%

 

能够得到第32位的成绩，可以心满意足了。

第一轮比赛文档

第二轮比赛文档

第二轮比赛平台

暂时没有上载我的程序，有需要的可以跟我联系。

由于这个工具写文章不是所见即所得。

在Problem2和Problem3中出现了很多空行，大家分析着看吧。

Problem #3: Solve Maze

Summary: 

You will create a class that can read a maze from a text file and find the shortest path through it.  The maze has a twist: some walls are “semi-permeable”; given a permeability index you can treat all or some of such walls as open space.

Specification:

You must create a file Problem3.[x], where x is the suffix required by the language of implementation (see section 2.2).  This file must compile (as defined in section 2.3) to Problem3.dll.

Your library must implement a Maze class, with one static method with the following signature; note that for simplicity, parameter types are given in C#.  However, you can use any of the languages listed in section 2.1 of this document.  To see the correct signature for other languages, see the relevant file in the Problem3\Sample\Code directory.

string SolveMaze(string inputFile,

            int permeabilityIndex);

The parameters are as follows:

inputFile: the path to a text file that contains a maze.  A maze file represents a 3 dimensional maze. A maze is always a cube of cells no larger than 25 x 25 x 25.  Every outside surface cell of the cube is a wall, and the start and goal state are always inside the surface layer of cells.  You may assume that the goal is always reachable from the start state. 

The maze will be represented as consecutive slices of the cube going downward, with each slice parallel to the top face when the cube is resting on a table.  Graphically, consider the following cube (cells are simply named for convenience):

不能贴图

Using the representation defined in this problem, the top two slices of the above cube would appear as follows:

First slice (top of the cube):

00000         ^ North

00000         |

00000         +-> East
00000
00000

Second slice (one level down):

00000
0S–0
0–00
0-PP0
00000

And so on.

A valid move is to go north, south, east, west, up, or down one cell.  Every move is the same distance, and a valid path to the goal state cannot go through any walls.  The following notation describes the maze:

• “0”    Wall Cell
• “S”   Start Cell
• “G”   Goal Cell
• “-”     Empty Cell
• “P”         Permeable Cell

permeabilityIndex:  an integer that is always non negative and less than or equal to the number of permeable cells in the cube.  The permeability index dictates how many permeable cells you can pass through in a solution.  Once you have used up your permeability index (passing through a permeable cell costs 1 unit) each permeable cell is effectively a wall. 

return value: this method should return a string that is the shortest path from the start cell to the goal cell.  There can be multiple paths with this shortest distance; any of these paths is acceptable.  The path should be a string of characters, each of which is either ‘N’, ‘S’, ‘E’, ‘W’, ‘U’, ‘D’ (for north, south, east, west, up and down respectively).  Looking down on the cube, the upper right of every slice is the north east corner.

Execution:

The harness (Problem3Harness.exe) for this problem takes a command-line argument (an integer) which is interpreted as the permeability index.  For example, “Problem3Harness.exe 2” will invoke the harness with a permeability index of 2. If you do not specify a permeability index on the command line, the permeability index defaults to zero. 

During execution, the harness performs the following steps:

• Calls the static method SolveMaze() in your DLL, with the path to the document and the permeability index you specified on the command line. 
• Creates an output file that contains the permeability index used, as well as the return value of the call to SolveMaze().  The harness will also create an output file that contains the execution time of your method.

 

Sample Data:

Problem3_Input.txt

00000 00000 00000 00000 00000 00000 0S–0 0–00 0-PP0 00000 00000 0P000 00000 0—0 00000 00000 0G–0 000-0 000-0 00000 00000 00000 00000 00000 00000

Problem3_Output.txt (permeability index param = 2)

Permeability Index: 2 DD

Problem3_Output.txt (permeability index param = 0)

Permeability Index: 0 SSDEEDNNWW

我的算法： 

两头同时进行的广度优先搜索法

在S点和G点同时开始

使用两棵树记录各自的路径

一个循环的内容为：

对比两棵树，取底层节点较少的一个作为搜索对象，对底层全部扩展一层。

扩展时查看是否已找到了一条通路，如果找到了，并且穿透次数不超过要求，此路即为最短路径。

否则，扩展后在迷宫相应格子作标记。

标记为：从S到此需要几步和几次穿透

或者从G到此需要几步和几次穿透

数据结构设计：

Class Cell用来描述迷宫，是迷宫的一个单元格。包含两个成员：一个值m_value表示单元格是墙壁还是通路（这里还有半透）；另一个标志m_mark标志曾经用了多少步到达这里。

搜索是从两端同时开始的。两棵搜索树，起点和终点分别是两棵树的根结点。从根结点开始扩展；每次选择一棵树，扩展一层，选择的是待扩展层节点较少的一棵树。

TreeNode结构就是树的一个节点：首先他要保存位置信息(l,r,c)，然后是父节点指针m_pi，到来的方向（从父节点到这里的方向）m_parent，到达的步数（也就是深度）m_st，和使用的穿透数m_pm。

当搜索到达某个节点时，要判断另一棵树是否已经到过这里，也就是是否已经得到了一条路径。这时检查的就是Cell的m_mark。

一般的迷宫这个m_mark只需要一个对象；而这里使用了数组，就是为了应付半透明墙的问题。考虑这样的情况：到达一个格子时，虽然步数增加了，但是使用穿透的次数减少了，这时就要保留这两个标记，并且两个节点都需要继续扩展下去。

当到达一个Cell时，要检查这个Cell的每个标记。如果标记为对端的，则看看总穿透次数有没有越限。如果是同一端的，则比较麻烦。

初始时假设这是一个需要增加的叶子。

1.        如果步数和穿透数都少了，则把该标记删掉（不可能发生）。

2.        否则如果穿透相等但是步数少了，则把此标记修改。

3.        否则如果步数也大，穿透也大，中止这次搜索。

4.        否则添加这个标记，添加这个节点。

再开始搜索下一个方向。

我的程序：

using System;
using System.IO;
using System.Collections;

namespace ImagineCup
{
 /*
 public enum direction
 {
  DOWN,
  SOUTH,
  EAST,
  UP,
  NORTH,
  WEST,
  NONE
 };
 */

 public struct Cell
 {
  public byte m_value; // 0 for wall, 1 for empty, 2 for p, 3 for start&goal
  public ArrayList m_mark;
 }
 /// <summary>
 /// m_pi means parent index, different from that in StepMark
 /// </summary>
 public class TreeNode
 {
  public sbyte m_l, m_r, m_c;
  public sbyte m_s; // source, enum SOURCE
  public short m_pi; // parent index
  public short m_parent; // parent dir, from parent to this
  public short m_st;
  public short m_pm;

  public TreeNode(sbyte level, sbyte row, sbyte col, short step, short permeance, short d, short parentindex, sbyte source)
  {
   m_l = level;
   m_r = row;
   m_c = col;
   m_parent = d;
   m_st = step;
   m_pm = permeance;
   m_pi = parentindex;
   m_s = source;
  }
 }
 /// <summary>
 /// Implement Maze class here.
 /// </summary>
 public class Maze
 {
  public const sbyte START = 1;
  public const sbyte GOAL = -1;

  static char [] dirname = new char[]{ ‘D’, ‘S’, ‘E’, ‘U’, ‘N’, ‘W’};
  static sbyte[,] dir = new sbyte[,]{
   {1, 0, 0},
   {0, 1, 0},
   {0, 0, 1},
   {-1, 0, 0},
   {0, -1, 0},
   {0, 0, -1},
  };
  public static Cell[,,] maze = new Cell[25,25,25];
  public static TreeNode[] StartTree = new TreeNode[65536];
  public static short SCount = 0;
  public static TreeNode[] GoalTree = new TreeNode[65536];
  public static short GCount = 0;
  public static short Sindex=0, Gindex=0;
  public static int AnswerStep = -1;
  public static int SAnswerInd = -1;
  public static int GAnswerInd = -1;
  public static char[] answer;
  /// <summary>
  /// VIP
  /// </summary>
  /// <param name="inputFile"></param>
  /// <param name="permeabilityIndex"></param>
  /// <returns></returns>
  public static string SolveMaze(string inputFile, int permeabilityIndex)
  {
   //
   // TODO: Implement SolveMaze
   //
   int nmarks = permeabilityIndex<4 ? 2*permeabilityIndex : 8;
   // ———- read maze matrix ———-
   StreamReader infile = new StreamReader(inputFile);
   sbyte level = 0, row = 0;
   string ln = infile.ReadLine();
   while(ln!=null)
   {
    for(sbyte col=0; col<ln.Length; col++)
    {
     maze[level, row, col].m_mark = new ArrayList(nmarks);
     if(ln[col]==’-')
     {
      maze[level, row, col].m_value = 1;
     }
     else if(ln[col]==’P'&&permeabilityIndex>0)
     {
      maze[level, row, col].m_value = 2;
     }
     else if(ln[col]==’S')
     {
      maze[level, row, col].m_value = 3;
      StartTree[SCount++] = new TreeNode(level, row, col, 0, 0, 6, -1, START);
      maze[level, row, col].m_mark.Add(StartTree[0]);
     }
     else if(ln[col]==’G')
     {
      maze[level, row, col].m_value = 3;
      GoalTree[GCount++] = new TreeNode(level, row, col, 0, 0, 6, -1, GOAL);
      maze[level, row, col].m_mark.Add(GoalTree[0]);
     }
    } // end of for(…
    if(ln.Length>0)
     row ++;
    else
    {
     row=0;
     level ++;
    }
    // read next line
    ln = infile.ReadLine();
   } // end of while(…
   infile.Close();
   level ++;
   //
   // ———- solve maze ———-
   //
   TreeNode[] CurTree = null;
   short orgcount, newcount;
   short i;
   sbyte curflag;
   while(AnswerStep==-1)
   {
    // 当开始树叶子少并且可扩展时
    if(SCount-Sindex <= GCount-Gindex)
    {
     CurTree = StartTree;
     orgcount = newcount = SCount;
     i = Sindex;
     curflag = START;
    }
    else
    {
     CurTree = GoalTree;
     orgcount = newcount = GCount;
     i = Gindex;
     curflag = GOAL;
    }
    // BFS : breadth first search
    if(orgcount==i)
     return("no way");
    for(;i<orgcount && AnswerStep==-1; i++)
    {
     // get all nodes adjacent to node[i]
     TreeNode tn = CurTree[i];
     for(byte d=0; d<6; d++)
     {
      byte mvalue = maze[tn.m_l+dir[d,0], tn.m_r+dir[d,1], tn.m_c+dir[d,2]].m_value;
      if(mvalue > 0)
      {
       short newpm = (short)(tn.m_pm + (mvalue==2?1:0));
       if(newpm > permeabilityIndex)
        continue;
       bool good = true;
       ArrayList alist = maze[tn.m_l+dir[d,0], tn.m_r+dir[d,1], tn.m_c+dir[d,2]].m_mark;
       TreeNode obj = null;
       for(int s=0; s<alist.Count; s++)
       {
        obj = (TreeNode)alist[s];
        if(obj.m_s == curflag) // same source
        {
         if(newpm < obj.m_pm && tn.m_st+1 == obj.m_st)
         {
          //alist.RemoveAt(s);
          good = false;
          obj.m_pm = newpm;
          obj.m_parent = d;
          obj.m_pi = i;
         }
         if(newpm >= obj.m_pm)
         {
          good = false;
          break;
         }
        }
        else
        {
         if(obj.m_pm + tn.m_pm <= permeabilityIndex) // the other side!!!!
         {
          AnswerStep = obj.m_st + tn.m_st + 1;
          if(curflag==START)
          {
           SAnswerInd = newcount;//CurTree.Count;
           //GAnswerInd = GoalTree.IndexOf(obj);
           GAnswerInd = Array.IndexOf(GoalTree, alist[s]);
          }
          else
          {
           //SAnswerInd = StartTree.IndexOf(obj);
           SAnswerInd = Array.IndexOf(StartTree, alist[s]);
           GAnswerInd = newcount;//CurTree.Count;
          }
          CurTree[newcount++] = new TreeNode((sbyte)(tn.m_l+dir[d,0]), (sbyte)(tn.m_r+dir[d,1]), (sbyte)(tn.m_c+dir[d,2]), (short)(tn.m_st+1), newpm, d, i, curflag);
          good = false;
          break;////////////////
         }
        } // end of if
       } // end of for(int s=0; s<alist.Count; s++)
       if(good)
       {
        CurTree[newcount++] = new TreeNode((sbyte)(tn.m_l+dir[d,0]), (sbyte)(tn.m_r+dir[d,1]), (sbyte)(tn.m_c+dir[d,2]), (short)(tn.m_st+1), newpm, d, i, curflag);
        alist.Add(CurTree[newcount-1]);
       }
       if(AnswerStep!=-1) break; // out of for(int d…
      } // end of if
     } // end of for(int d…
    } // end of for(;i<orgcount && …;i++)
    if(curflag==START)
    {
     Sindex = i;
     SCount = newcount;
    }
    else
    {
     Gindex = i;
     GCount = newcount;
    }
   }
   // DealWithAnswer
   answer = new char[AnswerStep];
   while(SAnswerInd>0)
   {
    answer[StartTree[SAnswerInd].m_st-1] = dirname[(int)((TreeNode)StartTree[SAnswerInd]).m_parent];
    SAnswerInd = StartTree[SAnswerInd].m_pi;
   }
   while(GAnswerInd>0)
   {
    answer[AnswerStep-GoalTree[GAnswerInd].m_st] = dirname[((int)((TreeNode)GoalTree[GAnswerInd]).m_parent+3)%6];
    GAnswerInd = GoalTree[GAnswerInd].m_pi;
   }
   return new string(answer);
  }
 }
}

点评：

大部分人使用BFS。有人使用了A*算法，但是不知道评估函数是什么。