这篇文章介绍了Atcoder - abc453_d Go Straight，分享给大家做个参考，收藏极客资料网收获更多编程知识

AT_abc453_d [ABC453D] Go Straight

写在前面

因为 \(Atcoder\) 没有提供 \(markdown\) 源码，所以我用的是洛谷的题面，没有中文。

为给大家带来的不便深表歉意。

（其实这些字只是为了凑齐中文字数，这样才能交上去）

题目描述

There is a grid of $ H $ rows $ \times $ $ W $ columns, and Takahashi moves through this grid up, down, left, and right.
The state of the cell at the $ i $ -th row from the top and $ j $ -th column from the left $ (1\leq i\leq H, 1\leq j\leq W) $ is represented by the character $ S_{i,j} $ .
$ S_{i,j} $ is one of #, ., o, x, S, G.

• If $ S_{i,j}= $ #: This cell cannot be entered.
• If $ S_{i,j}= $ .: This cell can be freely entered and exited. That is, after entering this cell, Takahashi can move to any adjacent cell (if it exists) in the up, down, left, or right direction.
• If $ S_{i,j}= $ o: In this cell, Takahashi must move in the same direction as the immediately preceding move. That is, after entering this cell, he must move to the next cell without changing direction.
• If $ S_{i,j}= $ x: In this cell, Takahashi cannot move in the same direction as the immediately preceding move. That is, after entering this cell, he must change direction to move to the next cell. Turning $ 180 $ degrees to return to the previous cell is considered as changing direction.
• If $ S_{i,j}= $ S: This cell is Takahashi's starting position. This cell can be freely entered and exited.
• If $ S_{i,j}= $ G: This cell is Takahashi's destination. This cell can be freely entered and exited.

There is exactly one $ (i,j) $ with $ 1\leq i\leq H, 1\leq j\leq W $ satisfying $ S_{i,j}= $ S, and exactly one satisfying $ S_{i,j}= $ G.

Takahashi wants to reach the destination by repeatedly moving to adjacent cells up, down, left, or right from his starting position.
Determine whether this is possible, and if so, output one valid sequence of moves with at most $ 5\times 10^6 $ moves between adjacent cells.
It can be proved that if a valid sequence of moves exists under the problem's conditions, then there exists one with at most $ 5\times 10^6 $ moves.
As long as the number of moves is at most $ 5\times 10^6 $ , it is not necessary to minimize the number of moves.

输入格式

The input is given from Standard Input in the following format:

$ H $ $ W $ $ S_{1,1} S_{1,2} \ldots S_{1,W} $ $ S_{2,1} S_{2,2} \ldots S_{2,W} $ $ \vdots $ $ S_{H,1} S_{H,2} \ldots S_{H,W} $

输出格式

If it is impossible to reach the destination while satisfying the conditions, output No on the first line, and nothing on the second line.
If it is possible to reach the destination while satisfying the conditions, output Yes on the first line.
On the second line, output a string $ T $ representing a sequence of moves. $ T $ must satisfy all of the following conditions.

• The length $ \lvert T\rvert $ of $ T $ is between $ 1 $ and $ 5\times 10^6 $ , inclusive.
• Each character of $ T $ is one of U, D, L, R.
  • The $ i $ -th character of $ T $ being U, D, L, R means that in the $ i $ -th move after departing, Takahashi moves to the adjacent cell above, below, to the left, or to the right, respectively.
• For $ 1\leq i\leq \lvert T\rvert $ , Takahashi is not outside the grid after the $ i $ -th move.
• During the moves, the conditions of each cell are not violated.
• After the $ \lvert T\rvert $ -th move, Takahashi is at the destination cell. As long as this condition is satisfied, he may pass through the destination cell before the $ \lvert T\rvert $ -th move.

输入输出样例 #1

输入 #1

3 5
.#...
.Sooo
..x.G

输出 #1

Yes
DRUUDDRR

输入输出样例 #2

输入 #2

3 3
#So
xoG
..#

输出 #2

Yes
DDLURR

输入输出样例 #3

输入 #3

2 2
So
oG

输出 #3

No

说明/提示

Sample Explanation 1

Let cell $ (i,j) $ denote the cell at the $ i $ -th row from the top and $ j $ -th column from the left.
Following the sample output, the path goes: cell $ (2,2) $ $ \to $ cell $ (3,2) $ $ \to $ cell $ (3,3) $ $ \to $ cell $ (2,3) $ $ \to $ cell $ (1,3) $ $ \to $ cell $ (2,3) $ $ \to $ cell $ (3,3) $ $ \to $ cell $ (3,4) $ $ \to $ cell $ (3,5) $ , reaching the destination.
Other solutions such as DRUURLRRDD are also accepted. On the other hand, since Takahashi cannot go straight through cell $ (3,3) $ , solutions such as DRRR are not accepted.

Sample Explanation 3

It is impossible to reach the destination while satisfying the conditions.

Constraints

• $ 1 \leq H,W\leq 1000 $
• $ S_{i,j} $ is one of #, ., o, x, S, G.
• There is exactly one $ (i,j) $ satisfying $ S_{i,j}= $ S and exactly one satisfying $ S_{i,j}= $ G.
• $ H $ and $ W $ are integers.

思路概述

一眼 \(搜索\) 。 我用的是 \(DFS\) ；

我们用一个字符串来记录走过的路径，在搜索时附加上方向。

如果当前只能继续往前走 ， 那么我们就只搜索向前。

如果我们不能再往前走，那么我们设置一个变量 ban ，表示不能走的方向。（特别地，如果当前在空地，ban是\(-1\)）。

理论正确，开⌨！

代码

#include <bits/stdc++.h>
#define maxn 1010
using namespace std;
const char ch[]={' ','R','D','L','U'};
const int dx[]={0,0,1,0,-1};
const int dy[]={0,1,0,-1,0};
int h,w,sx,sy,nx,ny;
char s[maxn][maxn];
bool vis[maxn][maxn][6];
string road;
bool F_end;
string op;
void dfs(int i,int j,short flag){
    if(i<1 || j<1 || i>h || j>w) return;
    if(vis[i][j][flag]) return;
    vis[i][j][flag]=true;
    if(F_end) return;
    if(s[i][j]=='#') return;
    if (s[i][j]=='G') {
        road=op;
        F_end=1;
        return;
    }
    if(s[i][j]=='o'){
        nx=i+dx[flag];
        ny=j+dy[flag];
        op+=ch[flag];
        dfs(nx,ny,flag);
        op.pop_back();
        return ;
    }
    short ban=-1;
    if(s[i][j]=='x') ban=flag;
    for(int k=1;k<=4;k++) {
        if(k==ban) continue;
        nx=i+dx[k];
        ny=j+dy[k];
        op+=ch[k];
        dfs(nx,ny,k);
        op.pop_back();
    }
}
int main() {
    cin>>h>>w;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>s[i][j];
            if(s[i][j]=='S') sx=i,sy=j;
        }
    }
    dfs(sx,sy,-1);
    if(!F_end){
        cout<<"No";
        return 0;
    }
    cout<<"Yes\n";
    cout<<road;
    return 0;
}

文章来源:https://www.cnblogs.com/naijil/p/19885598
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！