Code – 第269页

学霸的迷宫-蓝桥杯算法提高-广搜 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;

}

排列数（输出0~9的全排列）-蓝桥杯算法提高

问题描述

　　0、1、2三个数字的全排列有六种，按照字母序排列如下：
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个（第1个为0123456789）。

输入格式

　　一行，包含一个整数n

输出格式

　　一行，包含一组10个数字的全排列

样例输入

样例输出

0123456789

数据规模和约定

　　0 < n <= 10!
分析：啊我才发现有一个超好用的库函数……完全不用自己实现全排列。。竟然自己还那么笨的用下面的深度优先搜索的办法……next_permutation函数。。在algorithm里面，代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    string s = "0123456789";
    int n;
    cin >> n;
    int cnt = 1;
    do {
        if(cnt == n) {
            cout << s;
            break;
        }
        cnt++;
    }while(next_permutation(s.begin(), s.end()));
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

string s = "0123456789";

int n;

cin >> n;

int cnt = 1;

do {

if(cnt == n) {

cout << s;

break;

}

cnt++;

}while(next_permutation(s.begin(), s.end()));

return 0;

}

下面是那个笨方法。。。
假设有10个位置，需要在10个位置上依次放置0~9这十个数字。
1.先走到第一个位置，此时放置一个当前可以放置的数字当中最小的那个数字。
2.在走到第二个位置，放置一个当前可以放置的数字当中最小的那个数字。
…
3.到第10个位置时候，所有的数字已经放置完毕，属于第一个全排列。
4.收回第10个位置上的数字，此时还是只可以放置9，那么再到第9个位置面前，收回位置上的数字。
5.在第9个位置处，我们此时可以放置的数字有9，那么第10个位置放8.属于第二个全排列。
6.收回第10、9、8位置的数字，此时可以在第8个位置放置8.
…

用一个数组标记当前的数字是否已经被使用过了。
int book[10]; //一开始的时候没有被使用，初始化值为0.使用过了之后标记为1.
int a[10]; // 表示这10个需要放置数字的位置。
深度优先搜索：

void dfs(int step) {
    for (int i = 0; i <= 9; i++) {
        if (book[i] == 0) { //如果当前数字i没有被使用过
            a[step] = i; //就把当前位置放上这个数字i
            book[i] = 1; //同时不要忘记把book[i]标记为1
            dfs(step + 1); //深度优先搜索下一步
            book[i] = 0; //表示收回当前的数字
        }
    }
}


还有一个循环出口没有写。从step = 0开始执行，当当前的步骤已经step == 10的时候，
因为我们需要考虑的是0~9位置的摆放数字情况，当step时候不用执行，可以return作为出口了。
因为题目要求我们输出第n个全排列的组合是什么，那么
int cou = 0;
每当 step == 10 一组全排列完成的时候，
cou++;
直到 cou == n 的时候输出a数组中所有的数字。
所以代码描述为：


if (step == 10) {
    cou++;
    if (cou == n) {
        for (int i = 0; i <= 9; i++) {
            cout << a[i];
        }
    }
    return;
}


该题的解答完整代码如下：


#include <iostream>
using namespace std;
int n;
int book[10];
int a[10];
int cou = 0;
void dfs(int step) {
    if (step == 10) {
        cou++;
        if (cou == n) {
            for (int i = 0; i <= 9; i++) {
                cout << a[i];
            }
        }
        return;
    }
    
    for (int i = 0; i <= 9; i++) {
                if (book[i] == 0) {
                        a[step] = i;
                        book[i] = 1;
                        dfs(step + 1);
                        book[i] = 0;
                    }
            }
}

int main() {
        cin >> n;
        dfs(0);
      return 0;
}

void dfs(int step) {

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

if (book[i] == 0) { //如果当前数字i没有被使用过

a[step] = i; //就把当前位置放上这个数字i

book[i] = 1; //同时不要忘记把book[i]标记为1

dfs(step + 1); //深度优先搜索下一步

book[i] = 0; //表示收回当前的数字

}

还有一个循环出口没有写。从step = 0开始执行，当当前的步骤已经step == 10的时候，

因为我们需要考虑的是0~9位置的摆放数字情况，当step时候不用执行，可以return作为出口了。

因为题目要求我们输出第n个全排列的组合是什么，那么

int cou = 0;

每当 step == 10 一组全排列完成的时候，

cou++;

直到 cou == n 的时候输出a数组中所有的数字。

所以代码描述为：

if (step == 10) {

cou++;

if (cou == n) {

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

cout << a[i];

}

return;

}

该题的解答完整代码如下：

#include <iostream>

using namespace std;

int n;

int book[10];

int a[10];

int cou = 0;

void dfs(int step) {

if (step == 10) {

cou++;

if (cou == n) {

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

cout << a[i];

}

return;

}

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

if (book[i] == 0) {

a[step] = i;

book[i] = 1;

dfs(step + 1);

book[i] = 0;

}

int main() {

cin >> n;

dfs(0);

return 0;

}

在wordpress中使用 markdown：wp-markdown插件的使用方法

仪表盘 -> 插件 -> 安装插件 -> 搜索 wp-markdown.

下载该wordpress插件 -> 安装 -> 插件选项中启用wp-markdown插件
Snip20160202_235

启用：仪表盘 -> 设置 -> 撰写 -> Enable MarkDown for: 文章

Snip20160202_231

【note】Markdown语法说明

Markdown是一种可以使用普通文本编辑器编写的标记语言，通过简单的标记语法，它可以使普通文本内容具有一定的格式。

Markdown编辑器有很多种，我使用的是 Typora

以下是Markdown的基本语法～将下面的语法复制粘贴到Markdown编辑器里面就能看见效果啦～

*斜体*
_斜体第二种方法_


**加粗**
__加粗的第二种方法__


___粗斜体___


两个enter是换行，或者用</br>标签表示换行


用一行的=或者-表示一级标题和二级标题。如：
一级标题
=======
二级标题
--------


也可以在前面加上一到六个#表示标题的1级到6级，标题前加一个空格。如：
# 一级标题
## 二级标题
### 三级标题
#### 四级标题
##### 五级标题
###### 六级标题


无序列表：在前面加上 * 或者 + 或者 - 然后加个空格：
* ABC
* DEF
* GHI

+ JKL
+ MNO
+ PQR

- STU
- VWX
- YZZ


有序列表：数字+英文句点+空格。如下：
1. 呵呵
2. 哈哈
3. 嘿嘿
4. 哼哼


&lt;   // 会显示为”<“
&amp;  // 会显示为”&“：在 href 属性里面，必须将 & 转变为 &amp;
\.     // 为了防止产生"1."变为有序列表，则可以写成"1\."
 * _   // 如果 * 和 _ 两边都有空白的话，它们就只会被当成普通的符号。


>只在整个段落的第一行最前面加上大于号可以显示引用（此时出现引用形式，并且为斜体）。但是引言内如果要断行，那个空行也必须在前面加上大于号。就像下面写的酱紫：
>>区块引言也可以有级别，在前面加上不同数量的大于号即可。比如说这就是一个二级引言。
>>>这是一个三级引言。格式会显示为字体更小了。


```C++
代码块语法高亮
```


建立分割线的方法有：
* * *
*****
- - -
-------------------


超级链接：[超级链接显示的文字](超级链接的网址，可以是绝对路径、相对路径)
也支持HTML格式的超级链接<a href="https://www.baidu.com/">百度</a>


如果要标记一小段行内程序代码，可以用反引号把它包起来，像这样：
Use the `printf()` function.


插入图片：![图片的替换文字](图片的地址或路径)
![风景区图片](/Snip20160202_227.png)


Email邮件：
<123456789@qq.com>


锚点：(能够链接到某个一级标题)
[想要显示的名称](#锚点的名称)

*斜体*

_斜体第二种方法_

**加粗**

__加粗的第二种方法__

___粗斜体___

两个enter是换行，或者用</br>标签表示换行

用一行的=或者-表示一级标题和二级标题。如：

一级标题

=======

二级标题

--------

也可以在前面加上一到六个#表示标题的1级到6级，标题前加一个空格。如：

# 一级标题

## 二级标题

### 三级标题

#### 四级标题

##### 五级标题

###### 六级标题

无序列表：在前面加上 * 或者 + 或者 - 然后加个空格：

* ABC

* DEF

* GHI

+ JKL

+ MNO

+ PQR

- STU

- VWX

- YZZ

有序列表：数字+英文句点+空格。如下：

1. 呵呵

2. 哈哈

3. 嘿嘿

4. 哼哼

< // 会显示为”<“

& // 会显示为”&“：在 href 属性里面，必须将 & 转变为 &

\. // 为了防止产生"1."变为有序列表，则可以写成"1\."

* _ // 如果 * 和 _ 两边都有空白的话，它们就只会被当成普通的符号。

>只在整个段落的第一行最前面加上大于号可以显示引用（此时出现引用形式，并且为斜体）。但是引言内如果要断行，那个空行也必须在前面加上大于号。就像下面写的酱紫：

>>区块引言也可以有级别，在前面加上不同数量的大于号即可。比如说这就是一个二级引言。

>>>这是一个三级引言。格式会显示为字体更小了。

```C++

代码块语法高亮

```

建立分割线的方法有：

* * *

*****

- - -

-------------------

超级链接：[超级链接显示的文字](超级链接的网址，可以是绝对路径、相对路径)

也支持HTML格式的超级链接<a href="https://www.baidu.com/">百度</a>

如果要标记一小段行内程序代码，可以用反引号把它包起来，像这样：

Use the `printf()` function.

插入图片：![图片的替换文字](图片的地址或路径)

![风景区图片](/Snip20160202_227.png)

Email邮件：

<123456789@qq.com>

锚点：(能够链接到某个一级标题)

[想要显示的名称](#锚点的名称)

iOS开发控件不能绑定拖动到视图ViewController连接的解决方法

单击Main.storyboard,不能连接的视图最上方的 View Controller图标，将右侧Custom Class中的Class改为ViewController（或者当前视图所对应的 Class）

之后就可以愉快地继续按住 control 鼠标拖动到相应 View Controller 中进行连接了。

Snip20160131_213

Xcode误删Images.xcassets文件夹的恢复办法(Assets.xcassets)

Snip20160131_200

继续阅读Xcode误删Images.xcassets文件夹的恢复办法(Assets.xcassets)