poj 3984

　　题目：http://poj.org/problem?id=3984

　　思路：结构体(下标 + 路径方向) + bfs + queue(填充所有能走的路径) + stack(记录所有走过路径)

　　最后再遍历栈，通过到往终点的方向来判断，将栈中的其他路径排除。

　　代码：

#include <bits/stdc++.h>
using namespace std;
#define SIZE_X 5
#define SIZE_Y 5
struct Subs
{
	int i, j;
	int dir;
	Subs() {}
	Subs(int x, int y) : i(x), j(y) {}
	Subs(int x, int y, int dir) : i(x), j(y), dir(dir) {}
};
bool operator==(const Subs&pt, const Subs&pe)
{
	return pt.i == pe.i && pt.j == pe.j;
}
stack<Subs> bfs(int maze[][SIZE_Y], Subs ps, Subs pe)
{
	queue<Subs> q;
	stack<Subs> path;
	q.push(ps);
	while(!q.empty())
	{
		ps = q.front();
		q.pop();
		path.push(ps);
		maze[ps.i][ps.j] = 2;

		if (pos == pe)
		    return path;

		if (maze[ps.i + 1][ps.j] == 0 && ps.i + 1 < SIZE_X)
		{
		    Subs n(ps.i + 1, ps.j, 1); // down
		    q.push(n);
		}
		if (maze[ps.i][ps.j + 1] == 0 && ps.j + 1 < SIZE_Y)
		{
		    Subs n(ps.i, ps.j + 1, 2); // right
		    q.push(n);
		}
		if (maze[ps.i - 1][ps.j] == 0 && ps.i - 1 > -1)
		{
		    Subs n(ps.i - 1, ps.j, 3); // up
		    q.push(n);
		}
		if (maze[ps.i][ps.j - 1] == 0 && ps.j - 1 > -1)
		{
		    Subs n(ps.i, ps.j - 1, 4); // left
		    q.push(n);
		}
	}
	return path;
}
int main()
{
	Subs ps(0,0);
	Subs pe(4,4);
/*
	int maze[SIZE_X][SIZE_Y] = {
		0,1,0,0,0,
		0,1,0,1,0,
		0,0,0,0,0,
		0,1,1,1,0,
		0,0,0,1,0
	};
*/
	int maze[SIZE_X][SIZE_Y];
	for (int i = 0; i < SIZE_X; i++)
		for( int j = 0; j < SIZE_Y; j++)
			cin >> maze[i][j];
	stack<Subs> path = bfs(maze, ps, pe);
	stack<Subs> truepath;
	truepath.push(path.top());
	path.pop();
	
	while(!path.empty())
	{
		Subs n = path.top();
		path.pop();
		if (truepath.top().dir == 1 && 
			n.i + 1 == truepath.top().i && n.j == truepath.top().j)
				truepath.push(n);
		else if (truepath.top().dir == 2 && 
			n.i == truepath.top().i && n.j + 1 == truepath.top().j)
				truepath.push(n);
		else if (truepath.top().dir == 3 && 
			n.i - 1 == truepath.top().i && n.j == truepath.top().j)
				truepath.push(n);
		else if (truepath.top().dir == 4 && 
			n.i == truepath.top().i && n.j - 1 == truepath.top().j)
				truepath.push(n);
	}
	
	while (!truepath.empty())
	{
		printf("(%d,%d)
", truepath.top().i, truepath.top().j);
		truepath.pop();
	}
/*
	for(int i = 0; i < SIZE_X; i++)
	{
		for(int j = 0; j < SIZE_Y; j++)
		    printf("%d ", maze[i][j]);
		puts("");
	}
*/
	return 0;
}

　　Output:

$ ./test
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
2 1 2 2 0 
2 1 2 1 2 
2 2 2 2 2 
2 1 1 1 2 
2 2 2 1 2