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