UVA-816

Posted on | In , | Visitors:

This is my blog.
最近写了一些题
想想觉得没必要放上来
一来不经典，宁缺毋滥吧
二来懒，也觉得挺浪费时间的
听说明天可以升温了
感觉挺棒的
希望可以开太阳
最近事情还是挺多的
忙里偷闲
倒也不错
就这样吧

首先是讲讲UVA-816的这道题，这题重点不在于bfs，还是讲一些我觉得挺好的东西。
就不发送传送门了。

小记

  1. 方向与转向的统一
    通过一个顺序的排列，即顺时针或者逆时针，使得我不用去写if语句了。这个小技巧，其实很常见，但是在做题中能想到，就很好了。
  2. 字符与数值的转换
    很多时候，我们对数值能更好地进行计算，和理解。
  3. 结构体
    这个应该很多人的第一反应就是这个。
  4. 四维数组
    其实我心里对开三维及以上的数组是很担心的，所以一般不会去想这方面的应用。但事实是，在有多方面因素考虑，且某些方面的选择只有1、2个时，多维数组显得很方便，而且易理解
  5. 父节点
    这对于走迷宫要求出路径的问题来说，是很常见的。最后通过最后一个点倒回去，有些时候可以用递归，但显然很浪费，还可能会出现溢出的情况。在这题中，使用了vector
  6. 函数地运用
    好的代码都是代码块的。而且易理解，要培养自己的习惯。
  7. 输入
    这次的输入是我极少使用到的。用到了stringstream，这样对于后面不确定个数的输入，很简便。注意最后还有回车在流中，要清空。

发现在测试中，只可以读入文件。

AC代码（模仿紫书）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <cstdio>
#include <queue>
#include <sstream>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
const int maxn=100;
const char* dirs="NESW";
const char* turns="LRF";
int dirx[]={-1,0,1,0};
int diry[]={0,1,0,-1};
struct ty{
    int x,y,dir;
    ty(int _x,int _y,int _dir){
        x=_x;y=_y;dir=_dir;
    }//赋值，一般设置下划线
    ty(){}
};
int x0,y0,x1,y1,x2,y2;
char dir;
//int n,m;
int d[10][10][4];//最短路的长度
ty p[10][10][4];//父节点
bool has_edge[10][10][4][3];
//has_edge[r][c][dir][turn]表示(r,c,dir)状态下是否可沿turn拐
ll dir_id(char c){
    return strchr(dirs,c)-dirs;
}
ll turn_id(char c){
    return strchr(turns,c)-turns;
}
ty walk(const ty &u,int turn){
    int dir=u.dir;
    if(turn==0) dir=(dir+3)%4;//NESW->WNES
    if(turn==1) dir=(dir+1)%4;//NESW->ESWN
    
    return ty(u.x+dirx[dir],u.y+diry[dir],dir);
}
void print_ans(ty u){
    vector<ty>ans;
    for(;;){
        ans.push_back(u);
        if(d[u.x][u.y][u.dir]==0)break;
        u=p[u.x][u.y][u.dir];
    }
    
    ans.push_back(ty(x0,y0,dir));
    
    int cnt=0;
    for(int i=ans.size()-1;i>=0;i--){
        if(cnt%10==0)printf(" ");
        printf(" (%d,%d)",ans[i].x,ans[i].y);
        if(++cnt%10==0)printf("\n");
    }
    if(ans.size()%10!=0)printf("\n");
}
void solve(){
    queue<ty>q;
    int dirr=dir_id(dir);
    ty u(x1,y1,dirr);
    d[u.x][u.y][u.dir]=0;
    
    q.push(u);
    while(!q.empty()){
        ty u=q.front();
        q.pop();
        if(u.x==x2&&u.y==y2){//思考了一下，为什么先判断再决定是否塞入这个点，不是这样可以减少时间和空间嘛！难道是为了统一性
            print_ans(u);
            return ;
        }
        for(int i=0;i<3;i++){
            ty v=walk(u, i);
            if(has_edge[u.x][u.y][u.dir][i]&&d[v.x][v.y][v.dir]<0){//因为队列，所以之前的值肯定小
                d[v.x][v.y][v.dir]=d[u.x][u.y][u.dir]+1;
                p[v.x][v.y][v.dir]=u;
                q.push(v);
            }
        }
    }
    
    printf("  No Solution Possible\n");
}
int main() {
    //freopen("/Users/mrs_empress/Documents/oj/UVa/816/816/input","r",stdin);
    string name;
    while(cin>>name&&name!="END"){
        memset(d,-1,sizeof(d));
        memset(has_edge,0,sizeof(has_edge));
        memset(p,0,sizeof(p));
        
        cin>>x0>>y0>>dir>>x2>>y2;
        
        if(dir=='N'){x1=x0-1;y1=y0;}
        else if(dir=='E'){x1=x0;y1=y0+1;}
        else if(dir=='S'){x1=x0+1;y1=y0;}
        else{x1=x0;y1=y0-1;}
        
        getchar();//字符输入要特别小心
        string pos,str;
        stringstream ss;
        while(getline(cin, pos)&&pos!="0"){
            ss<<pos;
            int x,y;
            ss>>x>>y;
            while(ss>>str){
                if(str[0]=='*')break;
                int dir=dir_id(str[0]);
                int len=str.size();
                for(int i=1;i<len;i++){
                    int turn=turn_id(str[i]);
                    has_edge[x][y][dir][turn]=1;
                    //cout<<x<<" "<<y<<" "<<dir<<" "<<turn<<endl;
                }
            }
            ss.clear();
        }
        
        cout<<name<<endl;
        
        solve();
    }
    return 0;
}

其他

被一道题坑了，用了cin，cout就TLE了，换成scanf就对了，不应该起码要变成字符读入嘛。

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽