洛谷P6207-[USACO06OCT] Cows on Skates G(DFS记录路径)

简介: 洛谷P6207-[USACO06OCT] Cows on Skates G(DFS记录路径)

题目描述:


本题使用 Special Judge。


Farmer John 把农场划分为了一个 r 行 c 列的矩阵,并发现奶牛们无法通过其中一些区域。此刻,Bessie 位于坐标为 (1,1) 的区域,并想到坐标为 (r,c) 的牛棚享用晚餐。她知道,以她所在的区域为起点,每次移动至相邻的四个区域之一,总有一些路径可以到达牛棚。


这样的路径可能有无数种,请你输出任意一种,并保证所需移动次数不超过 100000。


输入格式:


第一行两个整数 r,c。


接下来 r 行,每行 c 个字符,表示 Bessie 能否通过相应位置的区域。字符只可能是 . 或 *。


. 表示 Bessie 可以通过该区域。

* 表示 Bessie 无法通过该区域。

输出格式:

若干行,每行包含两个用空格隔开的整数,表示 Bessie 依次通过的区域的坐标。


显然,输出的第一行是 1 1 ,最后一行是 r c。


相邻的两个坐标所表示的区域必须相邻。


样例输入:


5 8


..*...**


*.*.*.**


*...*...


*.*.*.*.


....*.*.


样例输出:


1 1


1 2


2 2


3 2


3 3


3 4


2 4


1 4


1 5


1 6


2 6


3 6


3 7


3 8


4 8


5 8


AC Code:  


#include<bits/stdc++.h>
using namespace std;
#define N 115
char a[N][N];//存入地图的数组 
bool vis[N][N];//标记数组 
int r,c,flag;
int placex[100001],placey[100001];//记录每走一步对应的横纵坐标 
int dx[]={0,0,1,-1};//定义两个方向数组 
int dy[]={1,-1,0,0};
bool judge(int x,int y) { 
  if(x>=1&&x<=r&&y>=1&&y<=c&&!vis[x][y]&&a[x][y]!='*') {
  //不越界,这个点没有走过,也不是围墙 
    return true;
  }
  return false;
}
void dfs(int x,int y,int step) {
  placex[step]=x;//这个点的横坐标存入此数组 
  placey[step]=y;//这个点的纵坐标存入此数组 
  vis[x][y]=1;//这个点标记为1,已经走过 
  if(x==r&&y==c) {//走到终点 
    for(int i=1;i<=step;i++) {//循环将所有步数对应的坐标输出 
      printf("%d %d\n",placex[i],placey[i]);
    }
  }
  for(int i=0;i<4;i++) {//四个方向搜索 
    int tx=x+dx[i];
    int ty=y+dy[i];
    if(judge(tx,ty)) {//判断该点是否符合下一步的要求 
      dfs(tx,ty,step+1);//继续下一个点的搜索,步数加1 
    }
  }
}
int main() {
  scanf("%d %d",&r,&c);
  for(int i=1;i<=r;i++) {
    for(int j=1;j<=c;j++) {
      scanf(" %c",&a[i][j]);//%前面的空格确保地图可以完整输入 
    }
  }
  dfs(1,1,1);//从第一个点(1,1)进入迷宫,步数为第一步 
  return 0;
}


相关文章
[USACO 2010 Feb S]Chocolate Eating
[USACO 2010 Feb S]Chocolate Eating
|
算法 C语言 C++
Til the Cows Come Home (USACO 2004 November)(Dijkstra算法)
Til the Cows Come Home (USACO 2004 November)(Dijkstra算法)
43 0
[USACO 2021.02 Feb]Problem 2. Comfortable Cows
[USACO 2021.02 Feb]Problem 2. Comfortable Cows
P2852 [USACO06DEC]牛奶模式Milk Patterns 后缀数组(poj3261)
P2852 [USACO06DEC]牛奶模式Milk Patterns 后缀数组(poj3261)
96 0
POJ3678——Katu Puzzle(2-SAT)
POJ3678——Katu Puzzle(2-SAT)
146 0
POJ3678——Katu Puzzle(2-SAT)
|
移动开发
洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G(01背包)
洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G(01背包)
洛谷P2639-[USACO09OCT]Bessie‘s Weight Problem G(01背包)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
洛谷P2871-[USACO07DEC]Charm Bracelet S(01背包模板题)
洛谷P1825-[USACO11OPEN]Corn Maze S(BFS)
洛谷P1825-[USACO11OPEN]Corn Maze S(BFS)
洛谷P1825-[USACO11OPEN]Corn Maze S(BFS)