题解 P6207 【[USACO06OCT]Cows on Skates G】
这题一看，妥妥的BFS嘛。
然鹅，窝秉承能深搜绝不广搜的想法，打了DFS（好久煤打忘得都差不多了）。
DFS想法：一条路走到黑，不行就返回。
蛋是，题目只需要窝们输出一条路径，所以窝们的book数组不需要取消标记（窝就是被这个坑了）。
注释详见代码。
代码
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
//定义r,c(如题)，输出路径用的数组，为了省事写的next数组和做标记的book数组。
int r,c,ax[13000],ay[13000],next[4][2]={{0,1},{1,0},{0,-1},{-1,0}},book[130][90];
char farm[130][90];//地图
bool f=false;//判断是否输出过路径的变量
void dfs(int x,int y,int step)
{
if(x < 1 || x > r || y < 1 || y > c) return ;//越界
if(book[x][y]) return ;//来过
if(farm[x][y] == '*') return ;//无法通行
if(f) return ;//输出过路径
if(x == r && y == c)//找到终点
{
for(int i=1;i<step;i++) printf("%d %d\n",ax[i],ay[i]);//输出，注意这里是i<step，因为窝们煤油把终点存进数组
printf("%d %d",r,c);//所以需要单独输出
f=true;//标记为以输出
return ;
}
ax[step]=x;ay[step]=y;//将当前点坐标存入数组
book[x][y]=1;//标记已走过
for(int i=0;i<4;i++)
{
dfs(x+next[i][0],y+next[i][1],step+1);//继续搜索
if(f) return ;//保险起见
}
return ;
}
int main()
{
scanf("%d %d",&r,&c);//输入
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++) cin >> farm[i][j];
dfs(1,1,1);//搜索
return 0;
}