1220.Look for homework SDNUOJ1220

Description

(the picture has no relation with this problem…I just want to add a picture. emmm…)

Super scholar robs the all homework of others. The monitor decides to combat with the super scholar so as to help students to get back the homework. But super scholar lives in a castle because he doesn’t want to be disturbed. The outside of the castle is a maze with two dimension grids. Entering the castle must pass the maze. The monitor needs to save time because of accompanying his girlfriend, so he wants to make a student named Huachao Wei help him who hasn’t a girlfriend. Now he has the map of the maze and needs to calculate the shortest path.
Input
The input consists several cases.For each case starts with two integers n,m(​),symbolizing the length and width of the maze.The next n lines contain m numbers with no space and value for only 0 and 1.The essence is that 0 can pass ,1 can’t pass. Now you are in the place of (1,1) refering to the top left corner.the export is in the place of (n,m).Each step can only walk with up,down,left and right.
Output
For each case,the first line prints the least number of steps to arrive the castle.The second line prints k characters for U,D,L,R,representing up,down,left,right.if there are many paths with the same length,please print the path with Minimum dictionary.It is guarantees that there must have a path for arriving the castle.
Sample Input
3 3
001
100
110
3 3
000
000
000
Sample Output
4
RDRD
4
DDRR

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

///保留路径不允许元素消失
///queue是删除性访问不符合条件
///所以用数组代替(省内存的事不考虑了)
struct node
{
    int x, y, pre;
    char s;
} a[105];

///图的界限
int n, m;
///移动方向(坐标系逆转90°)
int dx[] = { 1, 0, 0, -1};
int dy[] = { 0, -1, 1, 0};
char dir[] = {'D', 'L', 'R', 'U' };
///图的存储
string mp[11];
///访问标记
bool vis[11][11];
///路径存储
char c[105];
///搜索引导
int fro, bac;

void print(int i, int j);

void bfs(int x, int y)
{
    fro = 0;
    bac = 1;
    a[fro].x = x;
    a[fro].y = y;
    a[fro].pre = -1;
    vis[x][y] = 1;
    while(fro < bac)///小小的设计体现了队列的先进先出、穷竭搜索!
    {
        for(int i = 0; i < 4; ++i)
        {
            int temx = a[fro].x + dx[i];
            int temy = a[fro].y + dy[i];
            if(temx < 0 || temy < 0 || temx >= n || temy >= m || vis[temx][temy])
                continue;
            vis[temx][temy] = 1;
            a[bac].x = temx;
            a[bac].y = temy;
            a[bac].pre = fro;
            a[bac].s = dir[i];
            bac++;

            if(temx == n - 1 && temy == m - 1)
            {
                print(fro, bac - 1);
                return ;
            }
        }
        fro++;
    }
    return ;
}

void print(int i, int j)
{
    int tem = i;
    int len = 0;
    c[len++] = a[j].s;
    while(a[tem].pre != -1)
    {
        c[len++] = a[tem].s;
        tem = a[tem].pre;
    }
    cout << len << '\n';
    ///存了倒序的路径,自然要倒序输出
    for(int k = len - 1; k >= 0; --k)
    {
        cout << c[k];
    }
    cout << '\n';
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < n; ++i)
        {
            cin >> mp[i];
            for(int j = 0; j < m; ++j)
            {
                if(mp[i][j] == '1' )
                    vis[i][j] = 1;
                ///不可走的地方直接标记
            }
        }
        bfs(0, 0);
        memset(vis, 0, sizeof(vis));///满足多组输入
    }
    return 0;
}

全部评论

相关推荐

华泰证券信息技术部 软开 月base2.2w,年终要看当年收益,HR讲往年应届平均35W
点赞 评论 收藏
分享
喜提窑鸡一筐:简历排版有一些问题,如果没有排版能力建议直接在超级简历用现成模板(无广,建议超级简历看到结一下账,别有那些太花里胡哨的,简历架构按:教育背景,实习经历,项目经历,其他能力概述/获奖经历,教育背景简单写点说明学校专业,在读时间即可,GPA好看可以写上去,不好看不用写,背景整体篇幅占15%以内,大篇幅给实习经历和项目经历,项目经历别写太多废话,HR都懒得看,通常按项目目标,具体工作1.2.3点/涉及技术栈,项目成果这样结构化展开,如果没有实现经历最好是有2-3段项目经历,其他最后补充点个人能力综述and获奖经历即可
点赞 评论 收藏
分享
程序员小白条:简历有点拥挤,注意下排版和布局,奖项可以放项目上面,或者技术栈上面,主打一个学历+竞赛等方面,项目和技术栈这种大家包装太多了,但学历和竞赛这种实打实,虽然也有人造假,但 HR 喜欢具象化的东西
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务