codeforces 811 D. Vladik and Favorite Game（bfs水题）

题目链接：http://codeforces.com/contest/811/problem/D

题意：现在给你一个n*m大小的图，你输出一个方向之后，系统反馈给你一个坐标，表示走完这步之后到的位子，我们需要在2*n*m步之内走到终点，问怎样走才行（多解输出任意一个即可）。我们一开始的位子是（1,1），终点位子是“F”，‘*’表示不能走的位子，游戏开始的时候，有一些小伙伴比较调皮，会将U和D互换，就是说假设我们操作了U，但是实际是走到了D.或者也可能将L和R互换，当然也可能都没有互换过，当然也可能都互换过。然你模拟整个过程。

题解：其实很简单，先确定路线，然后在模拟，方向看他反馈的来确定有没有变，然后就是简单的模拟一下。

#include <iostream>

#include <queue>

#include <stack>

#include <cstring>

using namespace std;

char mmp[110][110];

struct TnT {

    int x , y;

}pre[110][110];

int dr[4][2] = {1 , 0 , -1 , 0 , 0 , 1 , 0 , -1} , n , m;

bool vis[110][110];

TnT bfs(TnT sta , TnT ed) {

    memset(vis , false , sizeof(vis));

    queue<TnT>q;

    q.push(sta);

    vis[sta.x][sta.y] = true;

    while(!q.empty()) {

        TnT gg = q.front();

        q.pop();

        if(gg.x == ed.x && gg.y == ed.y) {

            return gg;

        }

        for(int i = 0 ; i < 4 ; i++) {

            TnT gl = gg;

            gl.x += dr[i][0];

            gl.y += dr[i][1];

            if(gl.x >= 0 && gl.x < n && gl.y >= 0 && gl.y < m && mmp[gl.x][gl.y] != '*' && !vis[gl.x][gl.y]) {

                vis[gl.x][gl.y] = true;

                pre[gl.x][gl.y].x = gg.x;

                pre[gl.x][gl.y].y = gg.y;

                q.push(gl);

            }

        }

    }

    return ed;

}

int main() {

    cin >> n >> m;

    TnT sta , ed;

    for(int i = 0 ; i < n ; i++) {

        cin >> mmp[i];

        for(int j = 0 ; j < m ; j++) {

            if(mmp[i][j] == 'F') {ed.x = i , ed.y = j;}

        }

    }

    sta.x = 0 , sta.y = 0;

    TnT gg = bfs(sta , ed);

    stack<TnT>gl;

    while(gg.x != 0 || gg.y != 0) {

        gl.push(gg);

        int x = gg.x , y = gg.y;

        gg.x = pre[x][y].x;

        gg.y = pre[x][y].y;

    }

    cout << endl;

    TnT pos = sta;

    char ff[4] = {'L' , 'U' , 'D' , 'R'};

    bool flag[2];

    flag[0] = flag[1] = false;

    while(!gl.empty()) {

        TnT gb = gl.top();

        if(gb.y < pos.y) {

            cout << ff[0] << endl;

            int x , y;

            cin >> x >> y;

            x--,y--;

            if(x == gb.x && y == gb.y) {gl.pop() , pos = gb; continue;}

            else {

                if(!flag[0]) {

                    char cp = ff[0];

                    ff[0] = ff[3];

                    ff[3] = cp;

                    flag[0] = true;

                }

            }

        }

        if(gb.y > pos.y) {

            cout << ff[3] << endl;

            int x , y;

            cin >> x >> y;

            x--,y--;

            if(x == gb.x && y == gb.y) {gl.pop() , pos = gb; continue;}

            else {

                if(!flag[0]) {

                    char cp = ff[3];

                    ff[3] = ff[0];

                    ff[0] = cp;

                    flag[0] = true;

                }

            }

        }

        if(gb.x < pos.x) {

            cout << ff[1] << endl;

            int x , y;

            cin >> x >> y;

            x--,y--;

            if(x == gb.x && y == gb.y) {gl.pop() , pos = gb; continue;}

            else {

                if(!flag[1]) {

                    char cp = ff[1];

                    ff[1] = ff[2];

                    ff[2] = cp;

                    flag[1] = true;

                }

            }

        }

        if(gb.x > pos.x) {

            cout << ff[2] << endl;

            int x , y;

            cin >> x >> y;

            x--,y--;

            if(x == gb.x && y == gb.y) {gl.pop() , pos = gb; continue;}

            else {

                if(!flag[1]) {

                    char cp = ff[1];

                    ff[1] = ff[2];

                    ff[2] = cp;

                    flag[1] = true;

                }

            }

        }

    }

    return 0;

}

巴特西

codeforces 811 D. Vladik and Favorite Game（bfs水题）

最新文章

热门文章