Code – 第121页

蓝桥杯 ADV-147 算法提高学霸的迷宫

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

分析：用广度优先搜索解决。bfs。100分。如果用DFS可能会超时～

#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;
}

#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;

}

蓝桥杯 ADV-132 算法提高笨小猴

问题描述
　　笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
　　这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
输入格式
　　输入文件只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
输出格式
　　输出文件共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。
样例输入
error
样例输出
Lucky Word
2
样例说明
　　单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。
样例输入
olympic
样例输出
No Answer
0
样例说明
　　单词olympic中所有字母都只出现了1次，1-1=0，0不是质数。

#include <iostream>
#include <cctype>
using namespace std;
bool isprime(int n) {
    if(n <= 1)
        return false;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0)
            return false;
    }
    return true;
}

int main() {
    int maxn = -1, minn = 99999999;
    int a[26] = {0};
    string s;
    cin >> s;
    for(int i = 0; i < s.length(); i++) {
        char t = toupper(s[i]);
        a[t-'A']++;
    }
    for(int i = 0; i < 26; i++) {
        maxn = maxn > a[i] ? maxn : a[i];
        if(a[i] != 0)
            minn = minn < a[i] ? minn : a[i];
    }
    if(isprime(maxn-minn)) {
        cout << "Lucky Word" << endl << maxn - minn;
    } else {
        cout << "No Answer" << endl << 0;
    }
    return 0;
}

#include <iostream>

#include <cctype>

using namespace std;

bool isprime(int n) {

if(n <= 1)

return false;

for(int i = 2; i * i <= n; i++) {

if(n % i == 0)

return false;

}

return true;

}

int main() {

int maxn = -1, minn = 99999999;

int a[26] = {0};

string s;

cin >> s;

for(int i = 0; i < s.length(); i++) {

char t = toupper(s[i]);

a[t-'A']++;

}

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

maxn = maxn > a[i] ? maxn : a[i];

if(a[i] != 0)

minn = minn < a[i] ? minn : a[i];

}

if(isprime(maxn-minn)) {

cout << "Lucky Word" << endl << maxn - minn;

} else {

cout << "No Answer" << endl << 0;

}

return 0;

}

蓝桥杯 ADV-127 算法提高日期计算

问题描述
　　已知2011年11月11日是星期五，问YYYY年MM月DD日是星期几？注意考虑闰年的情况。尤其是逢百年不闰，逢400年闰的情况。
输入格式
　　输入只有一行
　　YYYY MM DD
输出格式
　　输出只有一行
　　W
数据规模和约定
　　1599 <= YYYY <= 2999
　　1 <= MM <= 12
　　1 <= DD <= 31，且确保测试样例中YYYY年MM月DD日是一个合理日期
　　1 <= W <= 7，分别代表周一到周日
样例输入
2011 11 11
样例输出
5

#include <iostream>
using namespace std;

int isleapyear(int year);
int days(int year, int month, int day);
int distance(int year, int month, int day);

int main() {
    int year, month, day;
    cin >> year >> month >> day;
    int distance1 = distance(year, month, day);
    if (year >= 2012) {
        switch(distance1) {
            case 0: cout << 6; break;
            case 1: cout << 7; break;
            case 2: cout << 1; break;
            case 3: cout << 2; break;
            case 4: cout << 3; break;
            case 5: cout << 4; break;
            case 6: cout << 5; break;
        }
    } else {
        switch(distance1) {
            case 0: cout << 6; break;
            case 1: cout << 5; break;
            case 2: cout << 4; break;
            case 3: cout << 3; break;
            case 4: cout << 2; break;
            case 5: cout << 1; break;
            case 6: cout << 7; break;
        }
    }
    return 0;
}

int isleapyear(int year) {
    if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
        return 1;
    else
        return 0;
}

int days(int year, int month, int day) {
    int sum = 0;
    if (month <= 2) {
        if (month == 1)
            sum = day;
        else
            sum = 31 + day;
    } else {
        switch(month) {
            case 3: sum = 59 + day; break;
            case 4: sum = 90 + day; break;
            case 5: sum = 120 + day; break;
            case 6: sum = 151 + day; break;
            case 7: sum = 181 + day; break;
            case 8: sum = 212 + day; break;
            case 9: sum = 243 + day; break;
            case 10: sum = 273 + day; break;
            case 11: sum = 304 + day; break;
            case 12: sum = 334 + day; break;
        }
        if(isleapyear(year) == 1) {
            sum = sum + 1;
        }
    }
    return sum;
}

int distance(int year, int month, int day) {
    int count = 0;
    int distance1 = 0;
    if(year >=2012) {
        distance1 = 365 * (year - 2012) + days(year, month, day);
        for (int i = 2012; i < year; i++) {
            if(isleapyear(i) == 1)
                count++;
        }
        distance1 = distance1 + count;
    } else {
        distance1 = 365 * (2011 - year) + 365 - days(year, month, day);
        if (isleapyear(year) == 1)
            distance1 = distance1 + 1;
        for (int i = year + 1; i <= 2011; i++) {
            if(isleapyear(i) == 1)
                count++;
        }
        distance1 = distance1 + count;
    }
    distance1 = distance1 % 7;
    return distance1;
}

#include <iostream>

using namespace std;

int isleapyear(int year);

int days(int year, int month, int day);

int distance(int year, int month, int day);

int main() {

int year, month, day;

cin >> year >> month >> day;

int distance1 = distance(year, month, day);

if (year >= 2012) {

switch(distance1) {

case 0: cout << 6; break;

case 1: cout << 7; break;

case 2: cout << 1; break;

case 3: cout << 2; break;

case 4: cout << 3; break;

case 5: cout << 4; break;

case 6: cout << 5; break;

}

} else {

switch(distance1) {

case 0: cout << 6; break;

case 1: cout << 5; break;

case 2: cout << 4; break;

case 3: cout << 3; break;

case 4: cout << 2; break;

case 5: cout << 1; break;

case 6: cout << 7; break;

}

return 0;

}

int isleapyear(int year) {

if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)

return 1;

else

return 0;

}

int days(int year, int month, int day) {

int sum = 0;

if (month <= 2) {

if (month == 1)

sum = day;

else

sum = 31 + day;

} else {

switch(month) {

case 3: sum = 59 + day; break;

case 4: sum = 90 + day; break;

case 5: sum = 120 + day; break;

case 6: sum = 151 + day; break;

case 7: sum = 181 + day; break;

case 8: sum = 212 + day; break;

case 9: sum = 243 + day; break;

case 10: sum = 273 + day; break;

case 11: sum = 304 + day; break;

case 12: sum = 334 + day; break;

}

if(isleapyear(year) == 1) {

sum = sum + 1;

}

return sum;

}

int distance(int year, int month, int day) {

int count = 0;

int distance1 = 0;

if(year >=2012) {

distance1 = 365 * (year - 2012) + days(year, month, day);

for (int i = 2012; i < year; i++) {

if(isleapyear(i) == 1)

count++;

}

distance1 = distance1 + count;

} else {

distance1 = 365 * (2011 - year) + 365 - days(year, month, day);

if (isleapyear(year) == 1)

distance1 = distance1 + 1;

for (int i = year + 1; i <= 2011; i++) {

if(isleapyear(i) == 1)

count++;

}

distance1 = distance1 + count;

}

distance1 = distance1 % 7;

return distance1;

}

蓝桥杯 ADV-119 算法提高 6-9删除数组中的0元素

编写函数CompactIntegers，删除数组中所有值为0的元素，其后元素向数组首端移动。注意，CompactIntegers函数需要接收数组及其元素个数作为参数，函数返回值应为删除操作执行后数组的新元素个数。
　　输入时首先读入数组长度，再依次读入每个元素。
　　将调用此函数后得到的数组和函数返回值输出。
样例输入
7
2 0 4 3 0 0 5
样例输出
2 4 3 5
4

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        int t;
        cin >> t;
        if(t != 0) {
            cout << t << " ";
            cnt++;
        }
    }
    cout << endl << cnt;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int cnt = 0;

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

int t;

cin >> t;

if(t != 0) {

cout << t << " ";

cnt++;

}

cout << endl << cnt;

return 0;

}

蓝桥杯 ADV-118 算法提高 3-2字符串输入输出函数

描述
　　编写函数GetReal和GetString，在main函数中分别调用这两个函数。在读入一个实数和一个字符串后，将读入的结果依次用printf输出。
　　两次输入前要输出的提示信息分别是”please input a number:\n”和”please input a string:\n”
样例输入
9.56
hello
样例输出
please input a number:
please input a string:
9.56
hello

#include <iostream>
using namespace std;
void GetReal() {
    cout << "please input a number:\n";
}

void GetString() {
    cout << "please input a string:\n";
}

int main() {
    GetReal();
    GetString();
    string n, s;
    cin >> n >> s;
    cout << n << endl << s;
    return 0;
}

#include <iostream>

using namespace std;

void GetReal() {

cout << "please input a number:\n";

}

void GetString() {

cout << "please input a string:\n";

}

int main() {

GetReal();

GetString();

string n, s;

cin >> n >> s;

cout << n << endl << s;

return 0;

}

蓝桥杯 ADV-112 算法提高 c++_ch02_01

编写一个程序，利用强制类型转换打印元音字母大小写10种形式的ASCII码。
　　输出的顺序为：大写的字母A，E，I，O，U的ASCII码，小写的字母a，e，i，o，u的ASCII码
所有的ASCII码都用十进制表示.输出10行,每行一个ASCII码，最后输出一个空行。

分析：static_cast<new type> (expression) 函数能够将括号中的表达式转换成new_type类型的数值，比如static_cast<int> (c[i])能将c[i]以int类型返回～

#include <iostream>
using namespace std;
int main() {
    char c[10] = {'A','E','I','O','U','a','e','i','o','u'};
    for (int i = 0; i < 10; i++)
        cout << static_cast<int> (c[i]) << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

char c[10] = {'A','E','I','O','U','a','e','i','o','u'};

for (int i = 0; i < 10; i++)

cout << static_cast<int> (c[i]) << endl;

return 0;

}