uva 816

65 阅读 0 评论 43 点赞

我是靠谱客的博主美好魔镜，最近开发中收集的这篇文章主要介绍uva 816，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：在这里插入图片描述

题解紫书主要部分讲的很清楚，但还是要自己实现一下，有好多细节需要注意

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <vector>

using namespace std;

char* s1 = "NESW";
char* s2 = "FLR";
int w[10][10][4],l[10][10][4][3]; //w表示这个状态到初始状态的距离
int sr,sc,er,ec,r0,c0,s_dir;
int d[4][2] = {-1,0,0,1,1,0,0,-1};
string name;

struct node
{
    int r,c,dir; //dir是当前朝向
    node() :r(), c(), dir(){}
    node(int r,int c,int dir):r(r),c(c),dir(dir){}
};

node p[10][10][4];

node turn(node a,int x)
{
    int dir = a.dir;
    if(x == 1) dir = (dir + 3) % 4;
    if(x == 2) dir = (dir + 1) % 4;
    return node(a.r + d[dir][0],a.c + d[dir][1],dir);
}

bool check(int r,int c)
{
    if(r > 0 && r < 10 && c > 0 && c < 10) return true;
    return false;
}

void print_ans(node a)
{
    vector<node> ans;
    ans.push_back(a);
    while(1){
        if(w[a.r][a.c][a.dir] == 0) break;
        node e = p[a.r][a.c][a.dir];
        ans.push_back(e);
        a = e;
    }

    ans.push_back(node(r0,c0,s_dir));
    int cnt = 0;
    for(int i = ans.size( )-1; i >= 0; i--) {
        if(cnt % 10 == 0) printf(" ");
        printf(" (%d,%d)", ans[i].r, ans[i].c);
        if(++cnt % 10 == 0) printf("n");
    }
    if(ans.size( ) % 10 != 0) printf("n");
}

void bfs()
{
    cout << name << endl;
    memset(w,-1,sizeof w);
    queue<node> q;
    node a = node(sr,sc,s_dir);
    q.push(a);
    w[sr][sc][s_dir] = 0;
    while(!q.empty()){
        node b = q.front();
        q.pop();
        if(b.r == er && b.c == ec){
            print_ans(b);
            return ;
        }
        for(int i = 0 ; i < 3 ; i++){
            a = turn(b,i);
            if(l[b.r][b.c][b.dir][i] && w[a.r][a.c][a.dir] < 0 && check(a.r,a.c)){
                w[a.r][a.c][a.dir] = w[b.r][b.c][b.dir] + 1;
                p[a.r][a.c][a.dir] = b;
                q.push(a);
            }
        }
    }
    printf("  No Solution Possiblen");
}

int main()
{
    while(cin >> name){
        if(name == "END") break;
        memset(l,0,sizeof l);
        char s[100];
        scanf("%d %d %s %d %d",&r0,&c0,s,&er,&ec);
        s_dir = strchr(s1,s[0]) - s1;
        sr = r0 + d[s_dir][0];
        sc = c0 + d[s_dir][1];
        int r,c;
        while(scanf("%d",&r) && r){
            scanf("%d",&c);
            while(scanf("%s",s)){
                if(strcmp(s,"*") == 0) break;
                int dir = strchr(s1,s[0]) - s1;
                int len = strlen(s);
                for(int i = 1; i < len ; i++){
                    int x = strchr(s2,s[i]) - s2;
                    l[r][c][dir][x] = 1;
                }
            }
        }
        bfs();
    }

    return 0;
}