Основы программирования

// golddist[i][j] - кратчайшее расстояние между золотым слитком [i] и золотым слитком [j]
// (если j<GOLDCNT) или конечной точкой (если j==GOLDCNT)
int golddist[GOLDCNT][GOLDCNT+1];
 
// вспомагательные массивы, благодаря которым можно удобно находить соседние клетки к данной.
// В данной программе (x+dx[k],y+dy[k]) это соответственно перемещения вниз, вверх, влево, вправо.
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
 
-----------------------------
 
// проверяем, является ли точка p точкой лабиринта, то есть она находится в прямоугольнике
// (0,0)->(0,width)->(height,width)->(height,0);
gboolean isgoodpoint(point p)
{
	return ((0<=p.x)&&(p.x<width))&&((0<=p.y)&&(p.y<height));
}
 
// Алгоритм для поиска кратчайшего пути в графе, в котором каждому ребру приписан вес 1
// ( в данном случае лабиринт можно представить как граф, в котором каждая клетка - вершина
// графа, и из каждой вершины есть рёбра в соседнюю веса 1, вес ребра - время перехода)
// переменная first была введена только для того, чтобы для генерации лабиринта можно было бы
// использовать тот же алгоритм, что и для поиска. Если first = true, то разрешается непроходимые
// клетки преобразовывать в проходимые с вероятностью 2/3. Возможность сделать клетку проходимой
// рассматривается только один раз
// Коротко алгоритм можно сформулировать так: Пока есть непосещенные достижимые вершины
// (очередь не пуста), посещаем очередную вершину и добавляем её соседей для обработки, если они
// ещё не были обработаны, или не находятся в очереди на обработку. Таким образом мы обойдём все
// вершины графа в порядке возрастания расстояния от начальной
void bfs(int startx,int starty,gboolean first)
{
	//создадим очередь вершин и добавим в неё начальную
	//скажем, что расстояние от начальной до начальной вершины равно 0 и предыдущей для начальной нет
	queue q;
	initqueue(&q);
	point cur,tmp;
	cur.x=startx;
	cur.y=starty;
	dist[starty][startx]=0;
	prev[starty][startx].x=-1;
	prev[starty][startx].y=-1;
	push(&q,cur);
	//пока мы не обработаем все вершины
	while(q.cnt!=0)
	{
		int k;
		//достаём вершину из очереди
		cur=pop(&q);
		for(k=0;k<4;k++)
		{
			//перебираем ей соседей и переходим в проходимые клетки, расстояние до которых не определено
			//если first = true, то возможно преобразование клетки лабиринта в проходимую
			tmp.x=cur.x+dx[k];
			tmp.y=cur.y+dy[k];
			if((isgoodpoint(tmp))&&(dist[tmp.y][tmp.x]==-1)&&((maze[tmp.y][tmp.x]!=wall)||(rand()%3!=0&&first)))
			{
				if(maze[tmp.y][tmp.x]==wall)
					maze[tmp.y][tmp.x]=empty;
				// говорим, что из cur вершины мы можем придти в tmp,
				// и расстояние от начальной вершины до вершины tmp на 1 больше
				dist[tmp.y][tmp.x]=dist[cur.y][cur.x]+1;
				prev[tmp.y][tmp.x]=cur;
				// добавляем вершину в обработку. Достижимые вершины будут добавлены в об
				push(&q,tmp);
			}
			else if(isgoodpoint(tmp)&&(dist[tmp.y][tmp.x]==-1))
			{
				// это условие предназначено для того, чтобы для вершины только один раз выбиралось,
				// будет ли она проходимой или нет.
				dist[tmp.y][tmp.x]=-5;
			}
		}
	}
}
 
-----------------------------
 
// вычислим расстояние от каждой клетки с золотом до каждой клетки с золотом и до конечной
for(i=0;i<GOLDCNT;i++)
{
	// очищаем массив расстояний и запускаем bfs из клетки с новым золотым слитком
	for(j=0;j<height;j++)
	{
		for(k=0;k<width;k++)
		{
			dist[j][k]=-1;
		}
	}
	bfs(goldpos[i].x,goldpos[i].y,FALSE);
	// после вызова расстояния сохранятся в массиве dist и поэтому их нужно только достать
	for(j=0;j<GOLDCNT;j++)
	{
		golddist[i][j]=dist[goldpos[j].y][goldpos[j].x];
	}
	golddist[i][GOLDCNT]=dist[endy][endx];
}

// Массивы, используемый для динамического программирования. dp[mask][last] означает следующее:
// мы уже взяли слитки, соотвествующие маске mask и стоим в точке, где был золотой слиток с номером
// last ( i-тый бит означает, был ли взят i-тый слиток; 1 - взят, 0 - не взят.
// dp[mask][last]=-1 означает, что это состояние ещё не было обработано
int dp[(1<<GOLDCNT)][GOLDCNT];
// next[mask][last] - показывает, куда лучше пойти в этом состоянии.
int next[(1<<GOLDCNT)][GOLDCNT];
 
-----------------------------
// функция, реализующая динамическое программирование для поиска кратчайшего пути, если были
// посещены золотые слитки, соответствующие маске mask (если в i-том бите стоит 1, мы посетили
// i-тый слиток), и сейчас находимся на месте слитка с номером last
int fdp(int mask,int last)
{
	//Если состояние ещё не было обработано
	if(dp[mask][last]==-1)
	{
		if(mask==(1<<GOLDCNT)-1)
		{
			// если мы посетили все золотые слитки, мы должны идти в конечную точку кратчайшим путём
			dp[mask][last]=golddist[last][GOLDCNT];
		}
		else
		{
			int i;
			for(i=0;i<GOLDCNT;i++)
			{
				if((mask&(1<<i))==0)
				{
				// если в маске i-тый бит равен 0 (золотой слиток не посещён), то мы пытаемся дойти до
				// него. (если это первый не посещённый золотой слиток, то мы просто сохраняем результат
				// перехода в dp[mask][last], иначе мы смотрим, является ли такой путь лучше)
					if(dp[mask][last]==-1||dp[mask][last]>fdp(mask|(1<<i),i)+golddist[last][i])
					{
						// мы запоминаем новый лучший результат и в какую клетку выгодно перейти
						dp[mask][last]=fdp(mask|(1<<i),i)+golddist[last][i];
						next[mask][last]=i;
					}
				}
			}
		}
	}
	return dp[mask][last];
}
-----------------------------
// говорим, что все состояния динамики являются необработанными
for(i=0;i<(1<<GOLDCNT);i++)
	for(j=0;j<GOLDCNT;j++)
		dp[i][j]=-1;
// запускаем алгоритм динамического программирования для случаев, когда мы посетили
// i-тую вершину и находимся сейчас в ней. Эти вызовы переберут все возможные состояния
for(i=0;i<GOLDCNT;i++)
	fdp((1<<i),i);

// выясним, какова длина самого короткого пути, который является решением задачи
distm=-1;
for(i=0;i<GOLDCNT;i++)
{
	// очевидно, что короткий путь будет состоять из перемещения к одному из слитков,
	// а потом от него к остальным, поэтому он может быть вычислен как
	// dist[goldpos[i].y][goldpos[i].x]+dp[1<<i][i]
	if(distm==-1||distm>dist[goldpos[i].y][goldpos[i].x]+dp[1<<i][i])
	{
		distm=dist[goldpos[i].y][goldpos[i].x]+dp[1<<i][i];
	}
}
// если золотых слитков не было, то тогда кратчайшее расстояние
// это путь из начальной точки в конечную
if(GOLDCNT==0)
{
	distm=dist[endy][endx];
}
 
printf("Best result:%d\n",distm);

int cnt=0;
// перерисуем лабиринт
expose_event(w,NULL,NULL);
int i,j,mind=-1,minidx,curmask,last;
point cur;
// очищаем информацию о расстоянии от вершины, для которой в прошлый раз был вызван bfs
for(i=0;i<height;i++)
{
	for(j=0;j<width;j++)
	{
		dist[i][j]=-1;
	}
}
// находим путь от текущей вершины до каждой достижимой при помощи bfs
bfs(curpos.x,curpos.y,FALSE);
// выбираем, к какому золотому слитку нам лучше идти, чтобы получить самый короткий путь
for(i=0;i<GOLDCNT;i++)
{
	// если i-тый слиток не был поднят и минимальное расстояние не определено или больше
	// чем то, которое мы можем достичь, пойдя к i-тому
	if((goldpicked&(1<<i))==0&&(mind==-1||mind>dist[goldpos[i].y][goldpos[i].x]+dp[goldpicked|(1<<i)][i]))
	{
		// говорим, что нам лучше пойти к i-тому слитку
		mind=dist[goldpos[i].y][goldpos[i].x]+dp[goldpicked|(1<<i)][i];
		minidx=i;
	}
}
// сохраним в curmask, какие слитки собраны на данный момент; last - куда лучше всего идти
// при слитках, которые собраны в соответствии с маской curmask; cur - точка, используемая для
// перебора вершин кратчайшего пути (предыдущее последнее положение)
curmask=goldpicked;
last=minidx;
cur.x=curpos.x;
cur.y=curpos.y;
// если ещё не все слитки собраны, то пытаемся куда-то перейти
while(curmask!=(1<<GOLDCNT)-1)
{
	//говорим, что мы посетили слиток с номером last и очищаем массив dist
	curmask|=(1<<last);
	for(i=0;i<height;i++)
	{
		for(j=0;j<width;j++)
		{
			dist[i][j]=-1;
		}
	}
	//находим кратчайший путь во все вершины из золотого слитка last
	bfs(goldpos[last].x,goldpos[last].y,FALSE);
	// отображаем путь из точки cur в точку goldpos[last]
	while(1)
	{
		// рисуем узел пути
		gdk_draw_arc(w->window,red,TRUE,10+cur.x*CELLSIZE-4+CELLSIZE/2,10+cur.y*CELLSIZE-4+CELLSIZE/2,8,8,0,64*360);
		if(prev[cur.y][cur.x].x==-1&&prev[cur.y][cur.x].y==-1) break;
		// если это не последняя вершина (а это можно определить по тому,
		// что у первой вершины нет предыдущей), то мы рисуем линию в предыдущую вершину,
		// иначе мы нарисовали весь путь
		gdk_draw_line(w->window,red,10+cur.x*CELLSIZE+CELLSIZE/2,10+cur.y*CELLSIZE+CELLSIZE/2,10+prev[cur.y][cur.x].x*CELLSIZE+CELLSIZE/2,10+prev[cur.y][cur.x].y*CELLSIZE+CELLSIZE/2);
		// перемещаемся в предыдущую в кратчайшем пути для текущей вершины клетку.
		cur=prev[cur.y][cur.x];
	}
	// запоминаем новое последнее положение и выбираем новую лучшую вершину, в которую лучше
	// всего пойти.
	cur.x=goldpos[last].x;
	cur.y=goldpos[last].y;
	last=next[curmask][last];
	}
// по той же схеме отрисовываем кратчайший путь из конечной точки в ту, из которой
// в последний раз был вызван bfs
cur.x=endx;
cur.y=endy;
while(1)
{
	gdk_draw_arc(w->window,red,TRUE,10+cur.x*CELLSIZE-4+CELLSIZE/2,10+cur.y*CELLSIZE-4+CELLSIZE/2,8,8,0,64*360);
	if(prev[cur.y][cur.x].x==-1&&prev[cur.y][cur.x].y==-1) break;
	gdk_draw_line(w->window,red,10+cur.x*CELLSIZE+CELLSIZE/2,10+cur.y*CELLSIZE+CELLSIZE/2,10+prev[cur.y][cur.x].x*CELLSIZE+CELLSIZE/2,10+prev[cur.y][cur.x].y*CELLSIZE+CELLSIZE/2);
	cur=prev[cur.y][cur.x];
}