回溯法+奇偶剪枝――Hdu 1010 Tempter of the Bone (二)

#include
#include
#include
#include

using namespace std;

#define MAXSIZE 10

int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};

char maze[MAXSIZE][MAXSIZE];
bool vis[MAXSIZE][MAXSIZE];
int dx, dy;
bool finished;

void InitMaze(int m, int n)
{
int i;
for (i = 0; i < m+2; i++)
{
maze[i][0] = maze[i][n+1] = 'X';
}
for (i = 0; i < n+2; i++)
{
maze[0][i] = maze[m+1][i] = 'X';
}
}

void Backtrack(int x, int y, int rt)
{
vis[x][y] = true;
if (x == dx && y == dy)
{
if (rt == 0)
{
finished = true;
}
}
else
{
int i;
for (i = 0; i < 4; i++)
{
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (!vis[nextx][nexty] && maze[nextx][nexty] != 'X')
{
Backtrack(nextx, nexty, rt-1);
if (finished)
{
return;
}
}
}
}
vis[x][y] = false;
}

struct Position
{
int x, y;
int nsteps;
};

int BFS(int x, int y)
{
queue next;
Position currPos = {x, y, 0};
next.push(currPos);
vis[x][y] = true;

while (!next.empty())
{
currPos = next.front();
next.pop();

if (currPos.x == dx && currPos.y == dy)
{
return currPos.nsteps;
}

int i;
for (i = 0; i < 4; i++)
{
Position nextPos = currPos;
nextPos.x += dir[i][0];
nextPos.y += dir[i][1];
if (!vis[nextPos.x][nextPos.y] && maze[nextPos.x][nextPos.y] != 'X')
{
nextPos.nsteps++;
next.push(nextPos);
vis[nextPos.x][nextPos.y] = true;
}
}
}
return -1;
}

int Dist(int x, int y)
{
return abs(dx-x)+abs(dy-y);
}

int main(void)
{
int m, n, t;
while (scanf("%d%d%d", &m, &n, &t) != EOF)
{
getchar();
if (m == 0 && n == 0 && t == 0)
{
break;
}

InitMaze(m, n);
int sx, sy;
int i, j;
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
maze[i][j] = getchar();
if (maze[i][j] == 'S')
{
sx = i;
sy = j;
}
if (maze[i][j] == 'D')
{
dx = i;
dy = j;
}
}
getchar();
}

finished = false;
if (Dist(sx, sy) % 2 == t % 2) //奇偶剪枝
{
memset(vis, false, sizeof(vis));
int minNSteps = BFS(sx, sy);
if (minNSteps != -1 && minNSteps <= t)
{
memset(vis, false, sizeof(vis));
Backtrack(sx, sy, t);
}
}
if (finished)
{
p