(输出路径搜索)[USACO06OCT] Cows on Skates G

题目描述

本题使用 Special Judge。

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

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

输入格式

第一行两个整数 ,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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=2020;
 4 int r,c;
 5 struct node{
 6     int x,y;
 7 };
 8 char mp[N][N];
 9 node pre[N][N];
10 bool vis[N][N];
11 int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
12 void bfs(int i,int j)
13 {
14     node str;
15     str.x=i,str.y=j;
16     queue<node>que;
17     que.push(str);
18     vis[i][j]=true;
19     while(!que.empty())
20     {
21         node now=que.front();
22         que.pop();
23         if(now.x==r&&now.y==c) return;
24         for(int i=0;i<4;i++)
25         {
26             node next;
27             next.x=now.x+dx[i],next.y=now.y+dy[i];
28             if(!vis[next.x][next.y]&&mp[next.x][next.y]!='*'&&next.x>0&&next.x<=r&&next.y>0&&next.y<=c)
29             {
30                 vis[next.x][next.y]=true;
31                 pre[next.x][next.y]=now;
32                 que.push(next);
33             }
34         }
35     }
36 }
37 void print(node cur)
38 {
39     if(cur.x==1&&cur.y==1) {cout<<"1 1"<<endl;return;}
40     print(pre[cur.x][cur.y]);
41     cout<<cur.x<<" "<<cur.y<<endl;
42 }
43 int main()
44 {
45     cin>>r>>c;
46     for(int i=1;i<=r;i++)
47         for(int j=1;j<=c;j++) cin>>mp[i][j];
48     bfs(1,1);
49     node ed;
50     ed.x=r,ed.y=c;
51     print(ed);
52     return 0;
53 }