INFOMAN брой 21
/*
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
Решение на задача LAB от второто контролно, Ямбол, 3 юни 2001 г.
----------------------------------------------------------------
Условие: Лабиринт има форма на правоъгълна мрежа от квадратчета с
N стълба и M реда (1 <= N, M <= 30). Всяко квадратче може да бъде:
'#' - стена;
'.' - празно, може да се преминава през него;
'S' - празно квадратче, в което се намира човек;
'B' - празно квадратче, в което се намира бъчва;
'Т' - празно квадратче, където трябва да бъде избутана бъчвата;
Задачата е човекът да избута бъчвата от началното квадратче ('B'),
то квадратчето означено с буквата 'T'. За тази цел човекът може да
извършва само следната операция: застава на празно квадратче (вляво,
вдясно, отгоре или отдолу на квадратчето, в което се намира бъчвата) и
я избутва на квадратчето, което е от противоположната страна (вдясно от
бъчвата, ако човекът се намира вляво, отлоду на бъчвата, ако се намира
отгоре и т.н.), ако то е празно. За движението си в лабиринта човекът
може да използва само празните квадратчета, като не може да минава през
квадратчето, в което в момента се намира бъчвата.
Напишете програма LAB.EXE, която намира преместване на бъчвата от
началното квадратче до квадратчето означено с 'T', което изисква възможно
най-малко избутвания на бъчвата, и ако има повече от една възможност, се
избира тази с най-малък брой движения на човека. Ако пак има повече от
една такава последователност, изведете само една от тях.
Вход: Входните данни ще бъдат в текстов файл с име LAB.IN. Първият ред
съдържа числата M и N. Всеки от останалите M реда съдържа низ с дължина
N,
в който могат да се срещат само знаците '#', '.', 'S', 'B' и 'T', като
'S', 'B', и 'T' се срещат само по един път в целия входен файл.
Изход: Единственият ред на файла LAB.OUT трябва да съдържа 'Impossible.',
ако не е възможно да се избута бъчвата до квадратчето означено с 'T',
в случай че е възможно, то редът трябва да съдържа низ състоящ се от
символите 'U', 'D', 'R', 'L', 'u', 'd', 'r' и 'l', където главните букви
означават избутване на бъчвата, а малките - преместване на човека в
съответната посока - нагоре, надолу, надясно, наляво.
Решение: Ще използваме търсене в ширина като критерий за дълбочината е
броя премествания на бъчвата. Да забележим, какви движения има смисъл да
прави човекът:
- преместване на квадратче съседно до бъчвата (само в началото);
- избутване на бъчвата;
- преместване от една страна на бъчвата до друга;
За да отчетем минималността на броя ходове на човека, за неговите
премествания също обхождаме лабиринта в ширина.
В опашката помним не само позицията на бъчвата, но и от коя нейна страна
се намира човекът. Пробваме да продължим движението в същата посока,
стига да е възможно. След това пробваме да преместим човека на някоя
друга страна спрямо бъчвата. Евентуално може и да се подобри броя
премествания на човека за дадена комбинация - позиция на бъчва и
разположение на човека спрямо нея (отгоре, отдолу, отляво или отдясно).
Обичайният подход да спрем търсенето в ширина, когато бъчвата достигне
квадратчето 'T' няма да свърши работа, т.к. може евентуално да подобрим
текущото решение с по-малък брой ходове на човека. За това, когато
бъчвата достигне квадратчето 'T' отбелязваме колко премествания на
бъчвата
са били използвани, и когато прочетем от опашката елемент с повече
премествания прекъсваме BFS-а.
Дотук беше основната част от задачата, но остана не по-малко трудното
възстановяване на пътя. Помнейки за всяка комб. позиция на бъчва и човек
на някоя страна до нея от коя предишна комб. сме дошли, можем да
възстановим само част от пътя - остават само преместванията на човека от
една страна на бъчвата до друга. За да намерим и тях първо обръщаме
наопаки масива с получения път така, че движейки се последователно по
него
да вървим от началното квадратче 'B' до целта 'T'. На всяка стъпка
проверяваме дали човекът е от същата страна на бъчвата, както и на
предишната стъпка. Ако е така значи имаме движение тип 'U', 'D', 'R' или
'L'. В противен случай човекът се е преместил от една страна на бъчвата
до
друга - пускаме отново търсене в ширина за пътя на човека и намираме
последователност от премествания 'u', 'd', 'r' и 'l'.
Коментар: Това решение спечели пълния брой точки на задачата като
работеше
сравнително бързо, изисквайки от порядъка на 256KB памет, поради
неточните
оценки за максимално възможна дължина на път в лабиринта.
Забележка: Във връзка с формата на списанието, вход/изходът на програмата
е променен (закоментарен) от LAB.IN / LAB.OUT, на LAB.C / екран.
Мартин Вълканов
E-mail: mvalkanov@yahoo.com
*/
#include <stdio.h>
#include <string.h>
#define MAX_N 30
#define MAX_M 30
#define FREE 0
#define WALL 1
#define UP 1
#define DOWN 2
#define LEFT 4
#define RIGHT 8
#define MAX_PATH_LEN 8192
int n, m;
char map[MAX_N][MAX_M];
int Tx, Ty, Bx, By, Sx, Sy;
int nTargetMoves = -1, nTargetHumanMoves, nTargetSide;
int nPathLen; char sPath[MAX_PATH_LEN];
typedef struct { char x, y; int nParentIdx, nMoves; } CHumanMoveCell;
typedef struct { char x, y; int nSide;
int nParentIdx, nMoves, nHumanMoves; } CBarrelMoveCell;
CHumanMoveCell vHumanMoveQueue[MAX_PATH_LEN];
char bHumanVisited[MAX_N][MAX_M];
int nIR_HMQ, nIW_HMQ;
CBarrelMoveCell vBarrelMoveQueue[MAX_PATH_LEN];
char bBarrelVisited[MAX_N][MAX_M];
int nIR_BMQ, nIW_BMQ;
int vSideReindex[9] = { 0, 0, 1, 0, 2, 0, 0, 0, 3 };
int nBarrelVisitedIdx[MAX_N][MAX_M][4];
int vBarrelIndexPath[MAX_PATH_LEN], nBarrelIndexPathLen;
char sHumanPath[MAX_PATH_LEN]; int nHumanPathLen;
void pMoveHuman( CHumanMoveCell * to, CHumanMoveCell * from )
{
to->nParentIdx = from - vHumanMoveQueue;
to->nMoves = from->nMoves + 1;
bHumanVisited[ to->x ][ to->y ] = 1;
}
int fCanMoveHuman( int tx, int ty, int sx, int sy )
{
int i;
CHumanMoveCell * x, * next;
if ( ( tx == sx ) && ( ty == sy ) ) return 0;
for ( i = 0; i < n; i++ ) memset( bHumanVisited[i], 0, m );
nIR_HMQ = 0; nIW_HMQ = 0;
vHumanMoveQueue[nIW_HMQ].x = sx; vHumanMoveQueue[nIW_HMQ].y = sy;
vHumanMoveQueue[nIW_HMQ].nParentIdx = -1;
vHumanMoveQueue[nIW_HMQ].nMoves = 0;
bHumanVisited[sx][sy] = 1;
nIW_HMQ++;
while ( nIR_HMQ != nIW_HMQ )
{
x = vHumanMoveQueue + nIR_HMQ; nIR_HMQ++;
if ( ( x->x > 0 ) && ( map[ x->x - 1 ][ x->y ] != WALL ) &&
( !bHumanVisited[ x->x - 1 ][ x->y ] ) )
{
next = vHumanMoveQueue + nIW_HMQ; nIW_HMQ++;
next->x = x->x - 1; next->y = x->y;
pMoveHuman( next, x );
if ( ( next->x == tx ) && ( next->y == ty ) ) return next->nMoves;
}
if ( ( x->x < n - 1 ) && ( map[ x->x + 1 ][ x->y ] != WALL ) &&
( !bHumanVisited[ x->x + 1 ][ x->y ] ) )
{
next = vHumanMoveQueue + nIW_HMQ; nIW_HMQ++;
next->x = x->x + 1; next->y = x->y;
pMoveHuman( next, x );
if ( ( next->x == tx ) && ( next->y == ty ) ) return next->nMoves;
}
if ( ( x->y > 0 ) && ( map[ x->x ][ x->y - 1 ] != WALL ) &&
( !bHumanVisited[ x->x ][ x->y - 1 ] ) )
{
next = vHumanMoveQueue + nIW_HMQ; nIW_HMQ++;
next->x = x->x; next->y = x->y - 1;
pMoveHuman( next, x );
if ( ( next->x == tx ) && ( next->y == ty ) ) return next->nMoves;
}
if ( ( x->y < m - 1 ) && ( map[ x->x ][ x->y + 1 ] != WALL ) &&
( !bHumanVisited[ x->x ][ x->y + 1 ] ) )
{
next = vHumanMoveQueue + nIW_HMQ; nIW_HMQ++;
next->x = x->x; next->y = x->y + 1;
pMoveHuman( next, x );
if ( ( next->x == tx ) && ( next->y == ty ) ) return next->nMoves;
}
}
return -1;
}
void pMoveBarrel( int x, int y, int nSide, CBarrelMoveCell * from, int
nMoves, int nHumanMoves )
{
CBarrelMoveCell * next;
int nOldVisit = nBarrelVisitedIdx[x][y][ vSideReindex[ nSide ] ];
if ( ( ( bBarrelVisited[x][y] & nSide ) == 0 ) ||
( ( nMoves == vBarrelMoveQueue[ nOldVisit ].nMoves ) &&
( nHumanMoves < vBarrelMoveQueue[ nOldVisit ].nHumanMoves ) ) )
{
bBarrelVisited[x][y] |= nSide;
nBarrelVisitedIdx[x][y][ vSideReindex[ nSide ] ] = nIW_BMQ;
next = vBarrelMoveQueue + nIW_BMQ; nIW_BMQ++;
next->x = x; next->y = y;
next->nSide = nSide;
next->nMoves = nMoves; next->nHumanMoves = nHumanMoves;
next->nParentIdx = ( from != NULL ) ? ( from - vBarrelMoveQueue ) : -1;
if ( ( next->x == Tx ) && ( next->y == Ty ) )
{
nTargetMoves = next->nMoves;
nTargetHumanMoves = next->nHumanMoves;
nTargetSide = next->nSide;
}
}
}
void pBFS( void )
{
CBarrelMoveCell * x;
int mx, my, cx, cy;
int nHumanMoves;
nIR_BMQ = 0; nIW_BMQ = 0;
map[Bx][By] = WALL;
if ( ( nHumanMoves = fCanMoveHuman( Bx, By - 1, Sx, Sy ) ) != -1 )
pMoveBarrel( Bx, By, UP, NULL, 0, nHumanMoves );
if ( ( nHumanMoves = fCanMoveHuman( Bx, By + 1, Sx, Sy ) ) != -1 )
pMoveBarrel( Bx, By, DOWN, NULL, 0, nHumanMoves );
if ( ( nHumanMoves = fCanMoveHuman( Bx - 1, By, Sx, Sy ) ) != -1 )
pMoveBarrel( Bx, By, LEFT, NULL, 0, nHumanMoves );
if ( ( nHumanMoves = fCanMoveHuman( Bx + 1, By, Sx, Sy ) ) != -1 )
pMoveBarrel( Bx, By, RIGHT, NULL, 0, nHumanMoves );
map[Bx][By] = FREE;
while ( nIR_BMQ != nIW_BMQ )
{
x = vBarrelMoveQueue + nIR_BMQ; nIR_BMQ++;
if ( ( nTargetMoves != -1 ) && ( x->nMoves > nTargetMoves ) ) break;
if ( ( x->nSide == UP ) && ( x->y < m - 1 ) && ( map[ x->x ][ x->y + 1 ] != WALL ) )
pMoveBarrel( x->x, x->y + 1, UP, x, x->nMoves + 1, x->nHumanMoves );
if ( ( x->nSide == DOWN ) && ( x->y > 0 ) && ( map[ x->x ][ x->y - 1 ] != WALL ) )
pMoveBarrel( x->x, x->y - 1, DOWN, x, x->nMoves + 1, x->nHumanMoves );
if ( ( x->nSide == LEFT ) && ( x->x < n - 1 ) && ( map[ x->x + 1 ][ x->y ] != WALL ) )
pMoveBarrel( x->x + 1, x->y, LEFT, x, x->nMoves + 1, x->nHumanMoves );
if ( ( x->nSide == RIGHT ) && ( x->x > 0 ) && ( map[ x->x - 1 ][ x->y ] != WALL ) )
pMoveBarrel( x->x - 1, x->y, RIGHT, x, x->nMoves + 1, x->nHumanMoves );
mx = 0; my = 0;
switch ( x->nSide )
{
case UP : my = -1; break;
case DOWN : my = +1; break;
case LEFT : mx = -1; break;
case RIGHT : mx = +1; break;
default : break;
}
cx = x->x + mx; cy = x->y + my;
map[ x->x ][ x->y ] = WALL;
if ( x->nSide != UP )
if ( ( nHumanMoves = fCanMoveHuman( x->x, x->y - 1, cx, cy ) ) != -1 )
pMoveBarrel( x->x, x->y, UP, x, x->nMoves, x->nHumanMoves + nHumanMoves );
if ( x->nSide != DOWN )
if ( ( nHumanMoves = fCanMoveHuman( x->x, x->y + 1, cx, cy ) ) != -1 )
pMoveBarrel( x->x, x->y, DOWN, x, x->nMoves, x->nHumanMoves + nHumanMoves );
if ( x->nSide != LEFT )
if ( ( nHumanMoves = fCanMoveHuman( x->x - 1, x->y, cx, cy ) ) != -1 )
pMoveBarrel( x->x, x->y, LEFT, x, x->nMoves, x->nHumanMoves + nHumanMoves );
if ( x->nSide != RIGHT )
if ( ( nHumanMoves = fCanMoveHuman( x->x + 1, x->y, cx, cy ) ) != -1 )
pMoveBarrel( x->x, x->y, RIGHT, x, x->nMoves, x->nHumanMoves + nHumanMoves );
map[ x->x ][ x->y ] = FREE;
}
}
void pGetHumanPath( int tx, int ty, int sx, int sy )
{
int i; CHumanMoveCell * x, * parent; char c;
if ( nHumanPathLen = fCanMoveHuman( tx, ty, sx, sy ) )
{
x = vHumanMoveQueue + ( nIW_HMQ - 1 );
for ( i = nHumanPathLen - 1; i >= 0; i-- )
{
parent = vHumanMoveQueue + x->nParentIdx;
if ( x->x == parent->x + 1 ) c = 'r'; else
if ( x->x == parent->x - 1 ) c = 'l'; else
if ( x->y == parent->y + 1 ) c = 'd'; else
if ( x->y == parent->y - 1 ) c = 'u';
sHumanPath[i] = c;
if ( i > 0 ) x = parent;
}
}
}
void pGetPath( void )
{
int i, t; CBarrelMoveCell * x, * parent;
int mx, my, cx, cy; char c;
int nBarrelIndexPathLen2;
int vSides[4] = { UP, DOWN, LEFT, RIGHT };
for ( i = 0; i < 4; i++ )
if ( ( t = nBarrelVisitedIdx[Tx][Ty][ vSideReindex[ vSides[i] ] ] ) != 0 )
if ( ( vBarrelMoveQueue[t].nMoves == nTargetMoves ) &&
( vBarrelMoveQueue[t].nHumanMoves < nTargetHumanMoves ) )
{
nTargetHumanMoves = vBarrelMoveQueue[t].nHumanMoves;
nTargetSide = vSides[i];
}
nBarrelIndexPathLen = 0;
x = vBarrelMoveQueue + nBarrelVisitedIdx[Tx][Ty][ vSideReindex[ nTargetSide ] ];
for (;;)
{
vBarrelIndexPath[ nBarrelIndexPathLen++ ] = x - vBarrelMoveQueue;
if ( x->nParentIdx == - 1 ) break;
x = vBarrelMoveQueue + x->nParentIdx;
}
nBarrelIndexPathLen2 = nBarrelIndexPathLen >> 1;
for ( i = 0; i < nBarrelIndexPathLen2; i++ )
{
t = vBarrelIndexPath[i];
vBarrelIndexPath[i] = vBarrelIndexPath[ nBarrelIndexPathLen - 1 - i ];
vBarrelIndexPath[ nBarrelIndexPathLen - 1 - i ] = t;
}
x = vBarrelMoveQueue + vBarrelIndexPath[0];
mx = 0; my = 0;
switch ( x->nSide )
{
case UP : my = -1; break;
case DOWN : my = +1; break;
case LEFT : mx = -1; break;
case RIGHT : mx = +1; break;
default : break;
}
cx = x->x + mx; cy = x->y + my;
if ( ( cx != Sx ) || ( cy != Sy ) )
{
map[ Bx ][ By ] = WALL;
pGetHumanPath( cx, cy, Sx, Sy );
map[ Bx ][ By ] = FREE;
memcpy( sPath + nPathLen, sHumanPath, nHumanPathLen );
nPathLen += nHumanPathLen;
sPath[ nPathLen ] = '\0';
}
for ( i = 1; i < nBarrelIndexPathLen; i++ )
{
x = vBarrelMoveQueue + vBarrelIndexPath[i];
parent = vBarrelMoveQueue + x->nParentIdx;
mx = 0; my = 0;
switch ( parent->nSide )
{
case UP : my = -1; c = 'D'; break;
case DOWN : my = +1; c = 'U'; break;
case LEFT : mx = -1; c = 'R'; break;
case RIGHT : mx = +1; c = 'L'; break;
default : break;
}
cx = parent->x - mx; cy = parent->y - my;
if ( ( x->nSide == parent->nSide ) && ( x->x == cx ) && ( x->y == cy ) )
sPath[ nPathLen++ ] = c;
else
{
cx = parent->x + mx; cy = parent->y + my;
mx = 0; my = 0;
switch ( x->nSide )
{
case UP : my = -1; break;
case DOWN : my = +1; break;
case LEFT : mx = -1; break;
case RIGHT : mx = +1; break;
default : break;
}
map[ x->x ][ x->y ] = WALL;
pGetHumanPath( x->x + mx, x->y + my, cx, cy );
map[ x->x ][ x->y ] = FREE;
memcpy( sPath + nPathLen, sHumanPath, nHumanPathLen );
nPathLen += nHumanPathLen;
sPath[ nPathLen ] = '\0';
}
}
}
int main( void )
{
int i, j; char sLine[MAX_N + 1];
// FILE * f = fopen( "lab.in", "r" );
char sTemp[200];
FILE * f = fopen( "lab.c", "r" ); fgets( sTemp, 200, f );
fscanf( f, "%d %d", &m, &n );
for ( i = 0; i < m; i++ )
{
fscanf( f, "%s", sLine );
for ( j = 0; j < n; j++ )
{
switch ( sLine[j] )
{
case 'T': Tx = j; Ty = i; sLine[j] = '.'; break;
case 'B': Bx = j; By = i; sLine[j] = '.'; break;
case 'S': Sx = j; Sy = i; sLine[j] = '.'; break;
default : break;
}
map[j][i] = ( sLine[j] == '#' ) ? WALL : FREE;
}
}
fclose(f);
pBFS();
if ( nTargetMoves != -1 ) pGetPath();
// f = fopen( "lab.out", "w" );
f = stdout;
fprintf( f, "%s", ( nPathLen ) ? sPath : "Impossible." );
fclose(f);
return 0;
}