蓝桥杯 – 第35页

蓝桥杯BASIC-28 基础练习 Huffuman树

问题描述
　　Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
　　给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
　　1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
　　2. 重复步骤1，直到{pi}中只剩下一个数。
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
　　本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

　　例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
　　1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
　　2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
　　3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
　　4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
　　5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
输入格式
　　输入的第一行包含一个正整数n（n<=100）。
　　接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出格式
　　输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9
样例输出
59

#include <iostream>
#include <vector>
#include <algorithm>
int cmp1(int a, int b) {
    return a > b;
}
using namespace std;
int main() {
    int n;
    int price = 0;
    vector<int> v;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }
    int size = v.size();
    while(size >= 2) {
        sort(v.begin(), v.end(), cmp1);
        int t = v[size-1] + v[size-2];
        price += t;
        v.pop_back();
        v.pop_back();
        v.push_back(t);
        size = v.size();
    }
    cout << price;
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

int cmp1(int a, int b) {

return a > b;

}

using namespace std;

int main() {

int n;

int price = 0;

vector<int> v;

cin >> n;

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

int temp;

cin >> temp;

v.push_back(temp);

}

int size = v.size();

while(size >= 2) {

sort(v.begin(), v.end(), cmp1);

int t = v[size-1] + v[size-2];

price += t;

v.pop_back();

v.push_back(t);

size = v.size();

}

cout << price;

return 0;

}

蓝桥杯-基础练习十六进制转八进制

问题描述
给定n个十六进制正整数，输出它们对应的八进制数。
输入格式
输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。
输出格式
输出n行，每行为输入对应的八进制正整数。
【注意】
输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。
样例输入
2
39
123ABC
样例输出
71
4435274
【提示】
先将十六进制数转换成某进制数，再由某进制数转换成八进制。
分析：先转成二进制，然后按3的倍数在前面补上0，然后转为对应的八进制，记得前面如果有0要去掉~

#include <iostream>
#include <map>
using namespace std;
int main() {
    string b, s, a;
    int n;
    cin >> n;
    string arr[16] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000",
        "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
    map<string, string> m;
    m["000"] = "0"; m["001"] = "1"; m["010"] = "2"; m["011"] = "3"; m["100"] = "4";
    m["101"] = "5"; m["110"] = "6"; m["111"] = "7";
    for(int i = 0; i < n; i++) {
        cin >> s;
        int lens = s.length();
        for(int j = 0; j < lens; j++) {
            if(s[j] > '9') {
                b += arr[s[j] - 'A' + 10];
            } else {
                b += arr[s[j] - '0'];
            }
        }
        int lenb = b.length();
        if(lenb % 3 == 1) {
            b = "00" + b;
        } else if(lenb % 3 == 2) {
            b = "0" + b;
        }
        int flag = 0;
        for(int j = 0; j < lenb; j += 3) {
            string temp = b.substr(j, 3);
            string t = m[temp];
            if(j == 0 && t == "0") {
                flag = 1;
                continue;
            }
            if(flag == 1 && j == 3 && t == "0") {
                continue;
            }
            cout << t;
        }
        cout << endl;
        b = "";
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

string b, s, a;

int n;

cin >> n;

string arr[16] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000",

"1001", "1010", "1011", "1100", "1101", "1110", "1111"};

map<string, string> m;

m["000"] = "0"; m["001"] = "1"; m["010"] = "2"; m["011"] = "3"; m["100"] = "4";

m["101"] = "5"; m["110"] = "6"; m["111"] = "7";

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

cin >> s;

int lens = s.length();

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

if(s[j] > '9') {

b += arr[s[j] - 'A' + 10];

} else {

b += arr[s[j] - '0'];

}

int lenb = b.length();

if(lenb % 3 == 1) {

b = "00" + b;

} else if(lenb % 3 == 2) {

b = "0" + b;

}

int flag = 0;

for(int j = 0; j < lenb; j += 3) {

string temp = b.substr(j, 3);

string t = m[temp];

if(j == 0 && t == "0") {

flag = 1;

continue;

}

if(flag == 1 && j == 3 && t == "0") {

continue;

}

cout << t;

}

cout << endl;

b = "";

}

return 0;

}

蓝桥杯历届试题-六角填数（12）

Snip20160318_79
第7题：六角填数（12）
如图所示六角形中，填入1~12的数字。
使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？
请通过浏览器提交答案，不要填写多余的内容。

answer：10
标记从上到下从左到右为1~12

#include <iostream>
using namespace std;
int book[13]; //标记1~12有没有被使用过
int a[13]; //标记12个位置所对应的数
int line[6];

void dfs(int x) {
	int i;
	//如果是已经填了数的那个，就直接跳过搜索下一个
	if(x == 1 || x == 2 || x == 12) {
		dfs(x + 1);
		return ;
	}
	//如果12个已经填满了，就判断是否满足每一条线上的都相等
	if(x > 12) {
		line[0] = a[1] + a[3] + a[6] + a[8];
		line[1] = a[1] + a[4] + a[7] + a[11];
		line[2] = a[8] + a[9] + a[10] + a[11];
		line[3] = a[2] + a[3] + a[4] + a[5];
		line[4] = a[2] + a[6] + a[9] + a[12];
		line[5] = a[5] + a[7] + a[10] + a[12];
		//判断是否两两相等，只要一层循环就好了
		//如果不相等，就直接return，说明这种情况不符合
		for(i = 1; i <= 5; i++) {
			if(line[i] != line[i - 1])
				return ;
		}
		//如果都满足，则输出a[6]的值
		cout << a[6] << endl;
		return ;
	}

	//从数字1到数字12，看有没有没填过的数字，没有填过就填入当前空格
	for(i = 1; i <= 12; i++) {
		if(book[i] == 0) {
			book[i] = 1;
			a[x] = i;
			//填入后就填下一个数字
			dfs(x + 1);
			book[i] = 0;
		}
	}
}


int main() {
	//根据题意初始化值
	book[1] = 1;
	book[3] = 1;
	book[8] = 1;
	a[1] = 1;
	a[2] = 8;
	a[12] = 3;

	dfs(1);
	return 0;
}

#include <iostream>

using namespace std;

int book[13]; //标记1~12有没有被使用过

int a[13]; //标记12个位置所对应的数

int line[6];

void dfs(int x) {

int i;

//如果是已经填了数的那个，就直接跳过搜索下一个

if(x == 1 || x == 2 || x == 12) {

dfs(x + 1);

return ;

}

//如果12个已经填满了，就判断是否满足每一条线上的都相等

if(x > 12) {

line[0] = a[1] + a[3] + a[6] + a[8];

line[1] = a[1] + a[4] + a[7] + a[11];

line[2] = a[8] + a[9] + a[10] + a[11];

line[3] = a[2] + a[3] + a[4] + a[5];

line[4] = a[2] + a[6] + a[9] + a[12];

line[5] = a[5] + a[7] + a[10] + a[12];

//判断是否两两相等，只要一层循环就好了

//如果不相等，就直接return，说明这种情况不符合

for(i = 1; i <= 5; i++) {

if(line[i] != line[i - 1])

return ;

}

//如果都满足，则输出a[6]的值

cout << a[6] << endl;

return ;

}

//从数字1到数字12，看有没有没填过的数字，没有填过就填入当前空格

for(i = 1; i <= 12; i++) {

if(book[i] == 0) {

book[i] = 1;

a[x] = i;

//填入后就填下一个数字

dfs(x + 1);

book[i] = 0;

}

int main() {

//根据题意初始化值

book[1] = 1;

book[3] = 1;

book[8] = 1;

a[1] = 1;

a[2] = 8;

a[12] = 3;

dfs(1);

return 0;

}

sqrt()在POJ ACM中Compile Error编译错误的问题

库函数里面的sqrt有三个原型
double sqrt(double);
float sqrt(float);
long double sqrt(long double);

没有int sqrt(int);
所以k=sqrt(x);改为k=sqrt((double)x);就可以通过编译了。
——度娘。ヾ(=^▽^=)ノ

库函数里面的sqrt有三个原型

double sqrt(double);

float sqrt(float);

long double sqrt(long double);

没有int sqrt(int);

所以k=sqrt(x);改为k=sqrt((double)x);就可以通过编译了。

——度娘。ヾ(=^▽^=)ノ

打印十字图-蓝桥杯历届试题

问题描述
小明为某机构设计了一个十字型的徽标（并非红十字会啊），如下所示：

对方同时也需要在电脑dos窗口中以字符的形式输出该标志，并能任意控制层数。

输入格式
一个正整数 n (n<30) 表示要求打印图形的层数。

输出格式
对应包围层数的该标志。

样例输入1
1

样例输出1

样例输入2
3

样例输出2

提示
请仔细观察样例，尤其要注意句点的数量和输出位置。

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int row = 9 + 4 * (n - 1);
    
    //init
    char a[150][150];
    for(int i = 1; i <= row; i++) {
        for (int j = 1; j <= row; j++) {
            a[i][j] = '.';
        }
    }
    int mid = row / 2 + 1;
    //中间十字架
    for (int i = mid - 2; i <= mid + 2; i++) {
        a[i][mid] = '$';
        a[mid][i] = '$';
    }
    
    //边框十字架
    int tn = n;
    while (tn != 0) {
        int trow = 9 + 4 * (tn - 1);
        // 第一行和最后一行，第一列和最后一列
        for (int i = mid - 2 * tn; i <= mid + 2 * tn; i++) {
            a[mid - 2 * (tn + 1)][i] = '$';
            a[mid + 2 * (tn + 1)][i] = '$';
            a[i][mid - 2 * (tn + 1)] = '$';
            a[i][mid + 2 * (tn + 1)] = '$';
        }
        
        //第二行和倒数第二行，第二列和倒数第二列
        a[mid - 2 * tn - 1][mid - 2 * tn] = '$';
        a[mid - 2 * tn - 1][mid + 2 * tn] = '$';
        a[mid - 2 * tn][mid - 2 * tn - 1] = '$';
        a[mid + 2 * tn][mid - 2 * tn - 1] = '$';
        
        a[mid + 2 * tn + 1][mid - 2 * tn] = '$';
        a[mid + 2 * tn + 1][mid + 2 * tn] = '$';
        a[mid - 2 * tn][mid + 2 * tn + 1] = '$';
        a[mid + 2 * tn][mid + 2 * tn + 1] = '$';
        
        //四个拐弯的角
        a[mid - 2 * tn][mid - 2 * tn] = '$';
        a[mid - 2 * tn][mid + 2 * tn] = '$';
        a[mid + 2 * tn][mid - 2 * tn] = '$';
        a[mid + 2 * tn][mid + 2 * tn] = '$';
        
        //上一层
        tn--;
    }
    
    
    //输出
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= row; j++) {
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int row = 9 + 4 * (n - 1);

//init

char a[150][150];

for(int i = 1; i <= row; i++) {

for (int j = 1; j <= row; j++) {

a[i][j] = '.';

}

int mid = row / 2 + 1;

//中间十字架

for (int i = mid - 2; i <= mid + 2; i++) {

a[i][mid] = '$';

a[mid][i] = '$';

}

//边框十字架

int tn = n;

while (tn != 0) {

int trow = 9 + 4 * (tn - 1);

// 第一行和最后一行，第一列和最后一列

for (int i = mid - 2 * tn; i <= mid + 2 * tn; i++) {

a[mid - 2 * (tn + 1)][i] = '$';

a[mid + 2 * (tn + 1)][i] = '$';

a[i][mid - 2 * (tn + 1)] = '$';

a[i][mid + 2 * (tn + 1)] = '$';

}

//第二行和倒数第二行，第二列和倒数第二列

a[mid - 2 * tn - 1][mid - 2 * tn] = '$';

a[mid - 2 * tn - 1][mid + 2 * tn] = '$';

a[mid - 2 * tn][mid - 2 * tn - 1] = '$';

a[mid + 2 * tn][mid - 2 * tn - 1] = '$';

a[mid + 2 * tn + 1][mid - 2 * tn] = '$';

a[mid + 2 * tn + 1][mid + 2 * tn] = '$';

a[mid - 2 * tn][mid + 2 * tn + 1] = '$';

a[mid + 2 * tn][mid + 2 * tn + 1] = '$';

//四个拐弯的角

a[mid - 2 * tn][mid - 2 * tn] = '$';

a[mid - 2 * tn][mid + 2 * tn] = '$';

a[mid + 2 * tn][mid - 2 * tn] = '$';

a[mid + 2 * tn][mid + 2 * tn] = '$';

//上一层

tn--;

}

//输出

for (int i = 1; i <= row; i++) {

for (int j = 1; j <= row; j++) {

cout << a[i][j];

}

cout << endl;

}

return 0;

}

学霸的迷宫-蓝桥杯算法提高-广搜 bfs 经典问题

问题描述
　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。
输入格式
　　第一行两个整数n， m，为迷宫的长宽。
　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。
输出格式
　　第一行一个数为需要的最少步数K。
　　第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。
<img src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" data-wp-more="more" data-wp-more-text="" class="wp-more-tag mce-wp-more" alt="" title="阅读更多…" data-mce-resize="false" data-mce-placeholder="1">


样例输入
Input Sample 1:
3 3
001
100
110

Input Sample 2:
3 3
000
000
000
样例输出
Output Sample 1:
4
RDRD

Output Sample 2:
4
DDRR
数据规模和约定
　　有20%的数据满足：1<=n,m<=10
　　有50%的数据满足：1<=n,m<=50
　　有100%的数据满足：1<=n,m<=500。

问题描述

　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释这件事情，于是就委托你帮他找一条最短的路线。

输入格式

　　第一行两个整数n， m，为迷宫的长宽。

　　接下来n行，每行m个数，数之间没有间隔，为0或1中的一个。0表示这个格子可以通过，1表示不可以。假设你现在已经在迷宫坐标(1,1)的地方，即左上角，迷宫的出口在(n,m)。每次移动时只能向上下左右4个方向移动到另外一个可以通过的格子里，每次移动算一步。数据保证(1,1)，(n,m)可以通过。

输出格式

　　第一行一个数为需要的最少步数K。

　　第二行K个字符，每个字符∈{U,D,L,R},分别表示上下左右。如果有多条长度相同的最短路径，选择在此表示方法下字典序最小的一个。

样例输入

Input Sample 1:

3 3

001

100

110

Input Sample 2:

3 3

000

样例输出

Output Sample 1:

RDRD

Output Sample 2:

DDRR

数据规模和约定

　　有20%的数据满足：1<=n,m<=10

　　有50%的数据满足：1<=n,m<=50

　　有100%的数据满足：1<=n,m<=500。

用广度优先搜索解决。bfs。100分。

#include <iostream>
using namespace std;
struct note {
    int x;
    int y;
    int f;
    int s;
    char dir;
};

int main() {
    char a[501][501];
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
        getchar();
    }
    int head = 1;
    int tail = 1;
    int book[501][501] = {0};
    book[1][1] = 1;
    
    int next[4][2] = {
        {1, 0},
        {0, -1},
        {0, 1},
        {-1, 0}
    };
    int tx = 1;
    int ty = 1;
    
    struct note que[250001];
    que[tail].x = 1;
    que[tail].y = 1;
    que[tail].f = 0;
    que[tail].s = 0;
    tail++;
    int flag = 0;
    while (head < tail) {
        for (int k = 0; k <= 3; k++) {
            tx = que[head].x + next[k][0];
            ty = que[head].y + next[k][1];
            
            if (tx < 1 || tx > n || ty < 1 || ty > m)
                continue;
            if (a[tx][ty] == '0' && book[tx][ty] == 0) {
                book[tx][ty] = 1;
                que[tail].x = tx;
                que[tail].y = ty;
                que[tail].f = head;
                que[tail].s = que[head].s + 1;
                if (k == 0) que[tail].dir = 'D';
                else if (k == 1) que[tail].dir = 'L';
                else if (k == 2) que[tail].dir = 'R';
                else if (k == 3) que[tail].dir = 'U';
                tail++;
            }
            if (tx == n && ty == m) {
                flag = 1;
                break;
            }
        }
        if (flag == 1) {
            break;
        }
        head++;
    }
    cout << que[tail - 1].s << endl;
    char t[250001];
    int temp = tail - 1;
    for (int i = que[tail - 1].s; i >= 1; i--) {
        t[i] = que[temp].dir;
        temp = que[temp].f;
    }
    for (int i = 1; i <= que[tail - 1].s; i++) {
        cout << t[i];
    }
    return 0;
}
[/cpp]

ps:

如果用深度优先搜索dfs，会超时。30分。
[cpp]
#include <iostream>
using namespace std;
char a[501][501];
int book[501][501];
int n, m;
int min1 = 999999;
char s[250001];
char t[250001];
void dfs(int x, int y, int step) {
    int next[4][2] = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };
    int tx, ty;
    if (x == n && y == m) {
        if (step < min1) {
            min1 = step;
            for (int i = 1; i <= min1; i++)
                s[i] = t[i];
        }
        return;
    }
    
    for (int k = 0; k <= 3; k++) {
        tx = x + next[k][0];
        ty = y + next[k][1];
        
        if (tx < 1 || ty < 1 || tx > n || ty > m)
            continue;
        if (a[tx][ty] == '0' && book[tx][ty] == 0) {
            book[tx][ty] = 1;
            if (k == 0) t[step] = 'D';
            if (k == 1) t[step] = 'L';
            if (k == 2) t[step] = 'R';
            if (k == 3) t[step] = 'U';
            dfs(tx, ty, step + 1);
            book[tx][ty] = 0;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
        getchar();
    }
    book[1][1] = 1;
    dfs(1, 1, 1);
    cout << min1 - 1 << endl;
    for (int i = 1; i < min1; i++) {
        cout << s[i];
    }
    
    return 0;
}

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

135

136

137

138

139

140

141

142

143

144

145

146

147

148

#include <iostream>

using namespace std;

struct note {

int x;

int y;

int f;

int s;

char dir;

};

int main() {

char a[501][501];

int n, m;

cin >> n >> m;

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

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

cin >> a[i][j];

}

getchar();

}

int head = 1;

int tail = 1;

int book[501][501] = {0};

book[1][1] = 1;

int next[4][2] = {

{1, 0},

{0, -1},

{0, 1},

{-1, 0}

};

int tx = 1;

int ty = 1;

struct note que[250001];

que[tail].x = 1;

que[tail].y = 1;

que[tail].f = 0;

que[tail].s = 0;

tail++;

int flag = 0;

while (head < tail) {

for (int k = 0; k <= 3; k++) {

tx = que[head].x + next[k][0];

ty = que[head].y + next[k][1];

if (tx < 1 || tx > n || ty < 1 || ty > m)

continue;

if (a[tx][ty] == '0' && book[tx][ty] == 0) {

book[tx][ty] = 1;

que[tail].x = tx;

que[tail].y = ty;

que[tail].f = head;

que[tail].s = que[head].s + 1;

if (k == 0) que[tail].dir = 'D';

else if (k == 1) que[tail].dir = 'L';

else if (k == 2) que[tail].dir = 'R';

else if (k == 3) que[tail].dir = 'U';

tail++;

}

if (tx == n && ty == m) {

flag = 1;

break;

}

if (flag == 1) {

break;

}

head++;

}

cout << que[tail - 1].s << endl;

char t[250001];

int temp = tail - 1;

for (int i = que[tail - 1].s; i >= 1; i--) {

t[i] = que[temp].dir;

temp = que[temp].f;

}

for (int i = 1; i <= que[tail - 1].s; i++) {

cout << t[i];

}

return 0;

}

[/cpp]

ps:

如果用深度优先搜索dfs，会超时。30分。

[cpp]

#include <iostream>

using namespace std;

char a[501][501];

int book[501][501];

int n, m;

int min1 = 999999;

char s[250001];

char t[250001];

void dfs(int x, int y, int step) {

int next[4][2] = {

{1, 0},

{-1, 0},

{0, 1},

{0, -1}

};

int tx, ty;

if (x == n && y == m) {

if (step < min1) {

min1 = step;

for (int i = 1; i <= min1; i++)

s[i] = t[i];

}

return;

}

for (int k = 0; k <= 3; k++) {

tx = x + next[k][0];

ty = y + next[k][1];

if (tx < 1 || ty < 1 || tx > n || ty > m)

continue;

if (a[tx][ty] == '0' && book[tx][ty] == 0) {

book[tx][ty] = 1;

if (k == 0) t[step] = 'D';

if (k == 1) t[step] = 'L';

if (k == 2) t[step] = 'R';

if (k == 3) t[step] = 'U';

dfs(tx, ty, step + 1);

book[tx][ty] = 0;

}

int main() {

cin >> n >> m;

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

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

cin >> a[i][j];

}

getchar();

}

book[1][1] = 1;

dfs(1, 1, 1);

cout << min1 - 1 << endl;

for (int i = 1; i < min1; i++) {

cout << s[i];

}

return 0;

}