2019年蓝桥杯C++B组

简单BFS算法

#include <iostream>
#include <algorithm>
#include <queue>
#include <string> 
using namespace std;

char mp[30][50];//地图 
bool vis[30][50];//标记该点是否走过
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}} ;//下，上，右，左
char dirc[4] = {'D','U','R','L'};

int n,m;

struct node{
    int x;
    int y;
    int step;
    string str;
}; 

queue<node> q;

bool check(int x,int y){
    if( x<0 || x>n || y<0 || y>m || vis[x][y] || mp[x][y]=='1' )
        return false;
    else return true; 
}

void bfs(int x,int y){
    node k = {x,y,0,""};
    q.push(k);
    vis[x][y] = true;
    while(!q.empty()){
     node now = q.front();
     if(now.x == n-1 && now.y == m-1 ){
         cout<<now.step<<endl;
         cout<<now.str<<endl;
         break;
     }
     q.pop();
     for(int i =0;i<4;i++){
     int nx = now.x + dir[i][0];
     int ny = now.y + dir[i][1];
     if(check(nx,ny)) {
         node news = {nx,ny,now.step+1,now.str+dirc[i]};
         q.push(news);
         vis[nx][ny] = true;
     }

    }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i<n;i++){
        scanf("%s",mp[i]);
    }
    bfs(0,0);
    return 0;
}
/*
26 50
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000 
11001000110101000010101100011010011010101011110111 
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000 
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110010
*/

把数据排好序，再每一位数据和min的差集，并用gcd（）得出最小公差d；

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int maxn = 1e5 + 5;

LL a[maxn];

int gcd(int x, int y){    //最大公倍数 
    return y==0 ? x : gcd(y,x%y);
}

int main(){
    int n;
    cin>>n;

    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i = 1; i < n; i++){
        a[i] -= a[0];
    }
    int d = a[1];
    for(int i = 2;i < n; i++){
        d = gcd(d,a[i]);
    }
    if(d == 0) cout<< n <<endl;
    else{
        cout<< a[n-1] / d +1 <<endl;
    }
    return 0;
}