看了一下，应该没人像我这样储存答案的。

这道题，是明显的搜索题。我比较喜欢用DFS。

这道题与其他题不同之处在于：这道题是Special Judge，走的路径有无数种可能，只要输出一种就够了！

所以，我们要将找出的路径存下来，这时，我们就不得不用上C++ STL库中的STACK(栈）了。

一.介绍一下栈

栈（stack）是C++ STL库中提供的数据结构之一。它是一种特殊的线性表，最大的特点是先进后出。也就是：先进的元素压入栈底，而后进的元素放在栈顶。

接下来我讲讲直接调用STL栈有哪些操作？

第一种：进栈操作（push）

第二种：出栈操作（pop）

第三种：返回长度（size）

第四种：判断是否为空（empty）

其他不多讲，因为在这道题中用不到！

哦对了，如果想普及的话，可以去这里学习，看一看伟大的百度百科是怎么写的！

二.关于这道题

深搜！

题目大意：我们要从(1,1)走到(n,m)，有障碍的地方不能走，并输出路径。

概括的是不是很简练？！

我们先列个思路吧

1.输入

2.dfs

3.输出路径

第一部分不说了……

dfs对图进行遍历，之所以要避免走重复点，是因为走重复没有意义，找到了做个标记，然后将点压入栈，返回，如果已经有解，就跳出。如果不会写搜索，建议先去做这题和这题。

最后讲一下栈部分，我对着代码解释吧。

while(!s.empty())//判断栈是否为空，如果空了，就不用继续做了
{
	ttt t=s.top();//提出栈顶元素
	s.pop();//栈顶元素出栈
	cout<<t.x<<' '<<t.y<<endl;//输出
}

最后，放代码（有注释）：

#include<bits/stdc++.h>
using namespace std;
struct ttt
{
	int x;
	int y;
};
stack<ttt>s;//栈，记录答案 
int n,m;//行数与列数 
char a[115][80];//输入进来的数组 
bool vis[115][80];//记录是否走过某点 
bool f;//记录是否找到解 
int dir[4][2]={1,0,0,1,-1,0,0,-1};//方向数组 
void dfs(int nx,int ny)
{
	if(nx==n&&ny==m)
	{
		f=true;//标记：已经找到解了 
		ttt now;
		now.x=nx;
		now.y=ny;
		s.push(now);//压入栈 
		return;//立刻返回 
	}
	int i;
	for(i=0;i<4;i++)
	{
		int dx,dy;
		dx=nx+dir[i][0];
		dy=ny+dir[i][1];
		if(dx>0&&dy>0&&dx<=n&&dy<=m&&!vis[dx][dy]&&a[dx][dy]!='*')//判断是否能走过去 
		{
			vis[dx][dy]=true;//标记已经去过 
			dfs(dx,dy);//继续搜索 
			vis[dx][dy]=false;//回溯 
			if(f)//如果找到解了 
			{
				ttt now;
				now.x=nx;
				now.y=ny;
				s.push(now);//压入栈 
				return;//立刻返回 
			}
		}
	}
}
int main()
{
	int i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j];//输入 
		}
	}
	vis[1][1]=true;//第一个点去过了 
	dfs(1,1);//开始搜索 
	while(!s.empty())//判断栈是否为空，如果空了，就不用继续做了
	{
		ttt t=s.top();//提出栈顶元素
		s.pop();//栈顶元素出栈
		cout<<t.x<<' '<<t.y<<endl;//输出
	}
    return 0;//结束程序 
}

还有，无注释版：

#include<bits/stdc++.h>
using namespace std;
struct ttt
{
	int x;
	int y;
};
stack<ttt>s;
int n,m;
char a[115][80];
bool vis[115][80];
bool f;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
void dfs(int nx,int ny)
{
	if(nx==n&&ny==m)
	{
		f=true;
		ttt now;
		now.x=nx;
		now.y=ny;
		s.push(now);
		return;
	}
	int i;
	for(i=0;i<4;i++)
	{
		int dx,dy;
		dx=nx+dir[i][0];
		dy=ny+dir[i][1];
		if(dx>0&&dy>0&&dx<=n&&dy<=m&&!vis[dx][dy]&&a[dx][dy]!='*')
		{
			vis[dx][dy]=true;
			dfs(dx,dy);
			vis[dx][dy]=false;
			if(f)
			{
				ttt now;
				now.x=nx;
				now.y=ny;
				s.push(now);
				return;
			}
		}
	}
}
int main()
{
	int i,j;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	vis[1][1]=true;
	dfs(1,1);
	while(!s.empty())
	{
		ttt t=s.top();
		s.pop();
		cout<<t.x<<' '<<t.y<<endl;
	}
    return 0;
}

最后说一句，这道题需要卡常，但是，只要用O2就行了！

THE END