解题报告 UVA816 Abbott的复仇 Abbott’s Revenge

题目内容

原文在文末,须认真阅读。

大意:给定一个迷宫,进入某个交叉点的方向不同,允许走出的方向也不同,求出从起点到终点的最短路并输出路径,如无解,输出 No Solution Possible

解题思路

思路就是一个 bfs,第一次到达终点时一定是最短路,遍历每个节点的时候存储上一个状态就可以逆推回去了。状态使用三元组 (r,c,dir) 表示。

但是此题需要注意很多细节:

  • 起点只能往起点规定的方向走,不能任意出发
  • IO 时的空格和换行问题
  • 方向的转换
  • (r_0,c_0,dir_0) 不能直接作为初始状态,需要先移动一格

代码的思路参照了紫书,p[r][c][dir] 存储此状态的上一个状态,d[r][c][dir] 存储到达此状态的最短路(相当于vis),has_edge[r][c][dir][turn] 存储当前状态能不能朝 turn 方向转弯。

思路很明了,注意细节即可,顺便吐槽 UVa 的毒瘤 IO,同时需要仔细阅读英文题面理解题面的意思。

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

using namespace std;

string maze_name;
int r0,c0,r1,c1,r2,c2;
char dir0;

struct node//bfs时的遍历状态
{
    int r,c,dir;//三元组存储
    node(){}
    node(int _r,int _c,int _dir)
    {
        r=_r,c=_c,dir=_dir;
    }
};

const char* dirs="NESW";
const char* turns="FLR";

inline int dir_id(char c)
{
    return strchr(dirs,c)-dirs;//将字母返回数字id
}

inline int turn_id(char c)
{
    return strchr(turns,c)-turns;//将字母返回数字id
}

inline bool chk(int r,int c)//防越界
{
    return 1<=r && r<=9 && 1<=c && c<=9;
}

const int dr[] = {-1,0,1,0};
const int dc[] = {0,1,0,-1};

bool has_edge[10][10][4][4];
node p[10][10][4];
int d[10][10][4];


inline node walk(const node &now,int turn)//返回某个状态转弯之后的状态
{
    int dir=now.dir;
    if(turn==1)//左转
        dir=(dir+3)%4;
    else if(turn==2)//右转
        dir=(dir+1)%4;
    return node(now.r+dr[dir],now.c+dc[dir],dir);//返回转完之后的状态
}

void print(node u)//打印路径
{
    vector<node> way;
    while(true)
    {
        way.push_back(u);//加入路径
        if(!d[u.r][u.c][u.dir])
            break;
        u=p[u.r][u.c][u.dir];//然后回溯上一个状态
    }
    way.push_back(node(r0,c0,dir_id(dir0)));
    int cnt=0;
    for(int i=way.size()-1;i>=0;i--)
    {
        if(cnt%10==0)
            cout<<' ';
        cout<<" ("<<way[i].r<<','<<way[i].c<<')';
        if(++cnt%10==0)
            cout<<endl;
    }
    if(way.size()%10)//注意io细节
        cout<<endl;
    return;
}

void bfs()
{
    cout<<maze_name<<endl;
    queue<node> q;
    memset(d,-1,sizeof d);
    memset(p,0,sizeof p);
    q.push(node(r1,c1,dir_id(dir0)));//先将初始状态加入
    d[r1][c1][dir_id(dir0)]=0;
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(now.r==r2 && now.c==c2)//到达终点
        {
            print(now);
            return;
        }
        for(int i=0;i<3;i++)//枚举转弯的方向
        {
            node to=walk(now,i);//转个弯
            if(has_edge[now.r][now.c][now.dir][i] && chk(to.r,to.c) && d[to.r][to.c][to.dir]<0)//判断是否合法
            {
                d[to.r][to.c][to.dir]=d[now.r][now.c][now.dir]+1;
                p[to.r][to.c][to.dir]=now;
                q.push(to);
            }
        }
    }
    cout<<"  No Solution Possible"<<endl;//注意行首空格
}

bool read_maze()
{
    memset(has_edge,0,sizeof has_edge);
    cin>>maze_name;
    if(maze_name=="END")
        return false;
    cin>>r0>>c0>>dir0>>r2>>c2;
    r1=r0+dr[dir_id(dir0)];//注意(r0,c0)不能直接作为初始状态
    c1=c0+dc[dir_id(dir0)];
    int r,c;
    string tmp;
    while(true)//读入迷宫的点
    {
        cin>>r;
        if(!r)
            break;
        cin>>c>>tmp;
        while(tmp!="*")
        {
            int dir=dir_id(tmp[0]);
            for(int i=1;i<tmp.size();i++)
                has_edge[r][c][dir][turn_id(tmp[i])]=true;
            cin>>tmp;
        }
    }
    bfs();
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    while(read_maze());
    return 0;
}

题目原文

Description

The 1999 World Finals Contest included a problem based on a dice maze. At the time the problem was written, the judges were unable to discover the original source of the dice maze concept. Shortly after the contest, however, Mr. Robert Abbott, the creator of numerous mazes and an author on the subject, contacted the contest judges and identified himself as the originator of dice mazes. We regret that we did not credit Mr. Abbott for his original concept in last years problem statement. But we arehappy to report that Mr. Abbott has offered his expertise to this years contest with his original and unpublished walk-through arrow mazes.
As are most mazes,a walk-through arrow maze is traversed by moving from intersection to intersection until the goal intersection is reached. As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited.
These directions are always left, forward or right, or any combination of these.
Figure 1 illustrates a walk-through arrow maze. The intersections are identified as (row, column) pairs, with the upper left being (1,1). The Entrance intersection for Figure 1 is (3,1), and the Goal intersection is (3,3). You begin the maze by moving north from (3,1). As you walk from (3,1) to (2,1), the sign at (2,1) indicates that as you approach (2,1) from the south (traveling north) you may continue to go only forward. Continuing forward takes you toward (1,1). The sign at (1,1) as you approach from the south indicates that you may exit(1,1) only by making a right. This turns you to the east now walking from (1,1) toward (1,2). So far there have been no choices to be made. This is also the case as you continue to move from (1,2) to (2,2) to (2,3) to (1,3). Now, however, as you move west from(1,3) toward (1,2), you have the option of continuing straight or turning left. Continuing straight would take you on toward (1,1), while turning left would take you south to (2,2). The actual(unique) solution to this maze is the following sequence of intersections: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).
You must write a program to solve valid walk-through arrow mazes. Solving a maze means (if possible) finding a route through the maze that leaves the Entrance in the prescribed direction, and ends in the Goal. This route should not be longer than necessary, of course.

Input

The input file will consist of one or more arrow mazes. The first line of each maze description contains the name of the maze, which is an alphanumeric string of no more than 20 characters. The next line contains, in the following order, the starting row, the starting column, the starting direction, the goal row, and finally the goal column. All are delimited by a single space. The maximum dimensions of a maze for this problem are 9 by 9, so all row and column numbers are single digits from 1 to 9.
The starting direction is one of the characters N, S, E or W, indicating north, south, east and west, respectively.
All remaining input lines for a maze have this format: two integers, one or more groups of characters, and a sentinel asterisk, again all delimited by a single space. The integers represent the row and column, respectively, of a maze intersection. Each character group represents a sign at that intersection. The first character in the group is N,S,E or W to indicate in what direction of travel the sign would be seen. For example,’S’ indicates that this is the sign that is seen when travelling south.(This is the sign posted at the north entrance to the intersection.) Following this first direction character are one to three arrow characters. These can be L,F or R indicating left, forward, and right, respectively.
The list of intersections is concluded by a line containing a single zero in the first column. The next line of the input starts the next maze, and so on. The end of input is the word END on a single line by itself.

Output

For each maze, the output file should contain a line with the name of the maze, followed by one or more lines with either a solution to the maze or the phrase No Solution Possible. Maze names should start in column 1, and all other lines should start in column 3,i.e., indented two spaces. Solutions should be output as a list of intersections in the format(R,C) in the order they are visited from the start to the goal, should be delimited by a single space, and all but the last line of the solution should contain exactly 10 intersections.

解题报告 P2901 [USACO08MAR]Cow Jogging G

题目内容

P2901

给定一有向带权图,求从 n 到 1 的前 k 短路的长度

解题思路

求 k 短路的一个常用的方法是使用 A*,怎么求呢?

首先,预处理出所有点到 1 的最短距离(使用反向图跑最短路),然后从 n 开始进行广搜,只不过队列改为优先队列,估价方式为 f+dis[now] 小的先出队,其中 f 为已经走过的路,dis[now]now 到 1 的最短距离,这样子进行估价可以使估的价一定小于等于实际代价。然后 A* 会根据估价从小到大依次进行扩展,最先进入到 1 号的就是最短路,随后次短路,第三短路。。。会依次进入到 1 号点,每次输出走过路径长即可。

#include <queue>
#include <cstdio>
#include <vector>
#include <cctype>
#include <utility>
#include <cstring>

typedef long long ll;
using namespace std;

const int maxn=1e3+5;

struct node
{
    ll pos,f;
    node(){}
    node(int _p,int _f)
    {
        pos=_p;
        f=_f;
    }
};

struct edge
{
    ll from,to,dist;
    edge(){}
    edge(ll u,ll v,ll w)
    {
        from=u;
        to=v;
        dist=w;
    }
};

//快读省略

vector<edge> g1[maxn],g2[maxn];//g1存正向图,g2存反向图
ll dis[maxn],n,m,k;
bool vis[maxn];

bool operator<(const node &_a,const node &_b)
{
    return _a.f+dis[_a.pos]>_b.f+dis[_b.pos];
}

void dijsktra()//反向跑dij获取每个点的距离
{
    priority_queue<pair<ll,ll>, vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
    memset(dis,0x3f,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int now=q.top().second;
        q.pop();
        if(!vis[now])
        {
            vis[now]=1;
            for(auto &e:g2[now])
            {
                if(dis[e.to]>dis[now]+e.dist)
                {
                    dis[e.to]=dis[now]+e.dist;
                    q.push(make_pair(dis[e.to],e.to));
                }
            }
        }
    }
    return;
}

void astar()//开始A*
{
    priority_queue<node> q;
    q.push(node(n,0));
    while(!q.empty())
    {
        ll now=q.top().pos,f=q.top().f;
        q.pop();
        if(now==1)//如果到终点了
        {
            printf("%lld\n",f);//直接输出
            if(!(--k))//如果已经求完前k短路,结束
                return;
        }
        else
            for(auto i:g1[now])//然后就是扩展
                q.push(node(i.to,i.dist+f));
    }
    while(k--)//如果还有没搞完的
        printf("-1\n");
    return;
}

inline void ins(ll u,ll v,ll w)
{
    g1[u].push_back(edge(u,v,w));
    g2[v].push_back(edge(v,u,w));
    return;
}

int main()
{
    n=read(),m=read(),k=read();
    ll u,v,w;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        ins(u,v,w);
    }
    dijsktra();
    astar();
    return 0;
}

解题报告 P5507 机关

题目内容

P5507

大意:这扇门上有一个机关,上面一共有12个旋钮,每个旋钮有4个状态,将旋钮的状态用数字1到4表示

每个旋钮只能向一个方向旋转(状态:1->2->3->4->1),在旋转时,会引起另一个旋钮也旋转一次(方向相同,不会引起连锁反应),同一旋钮在不同状态下,可能会引起不同的旋钮旋转(在输入中给出)

当所有旋钮都旋转到状态1时,机关就打开了

求最少打开门的次数

解题思路

搜索,但是由于极高的复杂度,肯定是不能用一般的搜索的。

然后可以使用 A*,卡卡常可以过去,A* 的估价函数设为当前步数加上旋钮与 1 差的步数之和除以二向上取整。因为考虑最优情况:转一个旋钮可以带动两个,所以这个估价函数是比较不错的。

A* 的实现使用优先队列即可,好像这题吸氧没什么卵用

判重由于我不写 hash,就搞了个 12 维的 bool 数组,计算器告诉我们空间能过(好了我要滚去学状态优化了)。

其实这题还可以用双向 bfs,因为初始状态和终止状态都是已知的

复杂度 O(玄学)

代码:

#include <cstdio>
#include <cctype>
#include <queue>
#define vis(x) (v[x.s[1]%4][x.s[2]%4][x.s[3]%4][x.s[4]%4][x.s[5]%4][x.s[6]%4][x.s[7]%4][x.s[8]%4][x.s[9]%4][x.s[10]%4][x.s[11]%4][x.s[12]%4])
using namespace std;

struct node
{
    int q[19];
    int s[13];
    int step;
    int chk;
};

inline void nxt(int &a)//将这个旋钮转一下
{
    a=(a+1)%4==0?4:(a+1)%4;
    return;
}

inline int read()
{
    char c=getchar();
    int s=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        s=10*s+c-'0',c=getchar();
    return s;
}

int a[13][5];
bool v[4][4][4][4][4][4][4][4][4][4][4][4];//巨长的 vis 数组

inline int h(node &x)//估价函数
{
    int ans=0;
    for(int i=1;i<=12;i++)
        ans+=x.s[i]==1?0:5-x.s[i];
    return (ans-1>>1)+1;
}

inline int check(node &x)//检查是否到达了最终状态
{
    for(int i=1;i<=12;i++)
        if(x.s[i]!=1)
            return false;
    return true;
}

bool operator>(const node &a,const node &b)//重载大于号
{
    return a.chk>b.chk;
}

void astar(node st)
{
    priority_queue<node,vector<node>,greater<node> > q;
    q.push(st);
    while(!q.empty())
    {
        node now=q.top();
        q.pop();
        if(check(now))
        {
            printf("%d\n",now.step);
            for(int i=1;i<=now.step;i++)
                printf("%d ",now.q[i]);
            return;
        }
        if(vis(now))
            continue;
        else
        {
            vis(now)=1;
            node nextone=now;
            for(int i=1;i<=12;i++)//状态转移
            {
                nxt(nextone.s[a[i][nextone.s[i]]]);
                nxt(nextone.s[i]);
                nextone.q[++nextone.step]=i;
                nextone.chk=h(nextone)+nextone.step;
                q.push(nextone);
                nextone.s[i]=now.s[i];
                nextone.s[a[i][nextone.s[i]]]=now.s[a[i][nextone.s[i]]];
                nextone.step--;
            }
        }
    }
}

int main()
{
    node st;
    for(int i=1;i<=12;i++)
    {
        for(int j=0;j<=4;j++)
            a[i][j]=read();
        st.s[i]=a[i][0];
    }
    st.chk=h(st);
    st.step=0;
    astar(st);
    return 0;
}

解题报告 P1126 机器人搬重物

题目内容

P1126

题面很长,大意就是控制一个机器人,但是这题最恶心的地方就是机器人的位置是点的坐标,但障碍物是格子

解题思路

这题调了我真的好久,是我见过最难调的搜索题之一,考验代码能力。从去年的 9 月份调了几个小时放弃之后直到今天再拿起此题,然后调半个小时过去了,其中两次 WA 一次是因为没判 -1,一次是因为判断边界的函数把 m 写成 n。

具体的思路就是,进行 bfs,每次转移的时候存储机器人左上角的坐标,判断障碍和越界的时候只需要判断他四个格子有没有障碍就可以了。然后就是一些 trick,比如采用 kln 和 kcol 数组来进行方便的向前移动的坐标转移,然后就是 vis 数组记得多开一维存储方向,再就是记得 x 和 y 分别代表的是行还是列,搞明白之后还是比较好写的。

查错真的是花了我不少时间,输出中间变量太香了,可以很方便的快速定位到错误的发生位置

然后这个狗东西其实也可以用双向搜索,但是我懒得用了,单向也可以过的

#include <cstdio>
#include <queue>
using namespace std;

int n,m;
//n is line, m is col
int sx,sy,fx,fy;//存起终点
int maze[52][52];//存迷宫
int kln[4][4],kcol[4][4];//第一维是朝向,第二维是要移动的步数
bool vis[52][52][4];//存储每个点的方向是否访问过

struct node
{
    int x,y;//机器人左上角坐标
    int face;//目前的朝向
    int step;//目前已经走的时间
    node(){}
    node(int _x,int _y,int _face,int _step)
    {
        x=_x;
        y=_y;
        face=_face;
        step=_step;
    }
};

queue<node> q;

void updk()//kln和kcol数组的初始化函数
{
    kln[1][1]=1,kln[1][2]=2,kln[1][3]=3;
    kln[3][1]=-1,kln[3][2]=-2,kln[3][3]=-3;
    kln[0][1]=kln[0][2]=kln[0][3]=0;
    kln[2][1]=kln[2][2]=kln[2][3]=0;
    kcol[1][1]=kcol[1][2]=kcol[1][3]=0;
    kcol[3][1]=kcol[3][2]=kcol[3][3]=0;
    kcol[0][1]=1,kcol[0][2]=2,kcol[0][3]=3;
    kcol[2][1]=-1,kcol[2][2]=-2,kcol[2][3]=-3;
    return;
}

inline bool isvalid(int x,int y)//判断一个机器人的位置是否合法
{
    if(x<1||x>n-1||y<1||y>m-1)//判边界,当时就是因为m写成n了WA第3个点
        return false;
    if(maze[x][y]||maze[x+1][y]||maze[x+1][y+1]||maze[x][y+1])//判障碍物
        return false;
    return true;
}

int bfs()
{
    int ans=0x3f3f3f3f;
    bool flag=0;
    while(!q.empty())
    {
        int nowx=q.front().x,nowy=q.front().y,nowdir=q.front().face,nowstep=q.front().step;
        q.pop();
        if(!isvalid(nowx,nowy))
            continue;
        if(nowx==fx && nowy==fy)
        {
            ans=nowstep<ans?nowstep:ans;
            flag=1;
        }
        if(!vis[nowx][nowy][(nowdir+1)%4])//这里是方向的处理,适当运用模运算可以简化思维
        {
            vis[nowx][nowy][(nowdir+1)%4]=1;//记得vis数组更新
            q.push(node(nowx,nowy,(nowdir+1)%4,nowstep+1));
        }
        if(!vis[nowx][nowy][(nowdir+3)%4])//一样的道理,换一个方向而已
        {
            vis[nowx][nowy][(nowdir+3)%4]=1;
            q.push(node(nowx,nowy,(nowdir+3)%4,nowstep+1));
        }
        for(int s=1;s<=3;s++)//枚举向前走的步数
        {
            int xx=nowx+kln[nowdir][s],yy=nowy+kcol[nowdir][s];
            if(!isvalid(xx,yy))//如果发现走1步不行就要及时break,否则WA
                break;
            if(!vis[xx][yy][nowdir])//如果没有重就加入队列
            {
                vis[xx][yy][nowdir]=1;
                q.push(node(xx,yy,nowdir,nowstep+1));
            }
        }
    }
    return flag?ans:-1;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&maze[i][j]);
    updk();
    char dir;
    scanf("%d %d %d %d %c",&sx,&sy,&fx,&fy,&dir);
    if(dir=='E') dir=0;
    if(dir=='S') dir=1;
    if(dir=='W') dir=2;
    if(dir=='N') dir=3;
    vis[sx][sy][dir]=1;
    q.push(node(sx,sy,dir,0));
    printf("%d\n",bfs());
    return 0;
}

这题细节还是很多的,可以锻炼代码能力和调试能力。

解题报告 洛谷P1379 八数码难题

题目内容

P1379

解题思路

这明显看上去就是一道搜索题(确认)。

我们知道输入的是初状态,123804765是末状态,初末状态都已知,于是想到可以进行双向bfs,从初末状态同时进行两个方向的bfs,可近似将复杂度降低为开根号。

具体的思路是:在同一个队列里进行同时扩展,使用两个map分别储存步数和访问状态,其中vis存储状态,1为从头出发访问的,2为从末状态访问的;step存储步数。

开头时定义了一个board数组用来储存棋盘,定义了两个函数进行9位数码和棋盘的转换(encode(int)和decode())。

每一次从队首取出一个数码时,先将其解压到board数组中方便操作,然后进行四个方向的扩展,将空格和其四个方向上的点进行交换,并使用chkboard()函数进行边界判断,在进行访问状态的判断,如果已经访问过了,就将正反向两次的步数加起来即为最终结果。

第一次写双向bfs,大佬勿喷

(真没想到这会是一道蓝题)

代码实现

#include <cstdio>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
int board[4][4];//存储棋盘使用
int nxt[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//方向操作数组
map<int,int> vis;//1为正向访问,2为反向访问
map<int,int> step;//存储该状态的步数

inline int encode()//将board数组转为9位数码
{
    int tmp=0;
    for(int i=1;i<4;i++)
        for(int j=1;j<4;j++)
        {
            tmp*=10;
            tmp+=board[i][j];
        }
    return tmp;
}

inline void decode(int code)//将9位码存储进board数组
{
    int tmp=1e8;
    for(int i=1;i<4;i++)
        for(int j=1;j<4;j++)
        {
            board[i][j]=code/tmp;
            code%=tmp;
            tmp/=10;
            //printf("%d ",board[i][j]);
        }
    return;
}

inline void getxy(int &x0,int &y0)//取出空格的坐标
{
    for(int i=1;i<4;i++)
        for(int j=1;j<4;j++)
            if(board[i][j]==0)
            {
                x0=i;
                y0=j;
                return;
            }
}

inline bool chkboard(int x,int y)//判断边界
{
    if(x<1||y<1||x>3||y>3)
        return false;
    return true;
}

int bfs(int fst)//bfs函数
{
    queue<int> q;
    q.push(fst);
    q.push(123804765);//将始末状态都入队
    vis[fst]=1;
    step[fst]=0;
    vis[123804765]=2;
    step[123804765]=0;//对两个map进行初始化
    while(!q.empty())
    {
        int cur=q.front();//取出队首元素
        decode(cur);
        q.pop();
        int x0,y0;
        getxy(x0,y0);//取出空格的位置
        for(int k=0;k<4;k++)
        {
            int xx=x0+nxt[k][0],yy=y0+nxt[k][1];
            if(!chkboard(xx,yy)) continue;//判断边界
            swap(board[xx][yy],board[x0][y0]);//进行移动棋子操作
            int now=encode();//将棋盘重新压回数码
            if(vis[now]==vis[cur])//判重,与上次相同的直接跳过
            {
                swap(board[xx][yy],board[x0][y0]);//一定要换回去
                continue;
            }
            if(vis[now]+vis[cur]==3)//如果发现此状态被对方访问过,直接出结果
            {
                return step[now]+step[cur]+1;
            }
            vis[now]=vis[cur];//否则继续bfs
            step[now]=step[cur]+1;
            q.push(now);
            swap(board[xx][yy],board[x0][y0]);//换回去
        }
    }
    return -1;//debug的时候用的
}

int main()
{
    int fst;
#ifndef ONLINE_JUDGE
    freopen("1379.in","r",stdin);//本地调试时使用
#endif
    scanf("%d",&fst);
    //printf("%d",fst);
    if(fst==123804765)//特判测试点#31
    {
        printf("0\n");
        return 0;
    }
    printf("%d\n",bfs(fst));
    return 0;
}

反思:

第一次写双向bfs的题,注重在状态的表示,有HASH的思想,使用一个9位的数字可以很方便的表示并存储状态。

双向bfs可以节约大量时间。(我用单向bfs竟然T了两个点,迷惑)