bfs
#include<bits/stdc++.h> using namespace std; int a[100][100],v[100][100]; struct point{ int x; int y; int step; }; queue<point>r; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; int main(){ int n,m,startx,starty,p,q; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } scanf("%d%d%d%d",&startx,&starty,&p,&q); point start; start.x=startx; start.y=starty; start.step=0; r.push(start); v[startx][starty]=1; int flag=0; while(!r.empty()){ int x=r.front().x,y=r.front().y; if(x==p&&y==q){ flag=1; printf("%d",r.front().step); break; } for(int k=0;k<=3;k++){ int tx,ty; tx=x+dx[k]; ty=y+dy[k]; if(a[tx][ty]==1&&v[tx][ty]==0){ point temp; temp.x=tx; temp.y=ty; temp.step=r.front().step+1; r.push(temp); v[tx][ty]=1; } } r.pop(); } if(flag==0) printf("no answer!"); return 0; }
dfs
#include<bits/stdc++.h> using namespace std; const int N=1e2+10; int mp[N][N],vis[N][N]; bool fg=false; int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int n; int sx,sy,ex,ey; // bool check(int nx,int ny){ // if(nx>0&&nx<n&&ny>0&&ny<=n&&vis[nx][ny]!=false&&mp[nx][ny]==0){ // return true; // } // return false; // } void dfs(int x,int y){ if(vis[x][y]||fg)return; vis[x][y]=true; if(x==ex&&y==ey){ fg=true; return; } for(int i=0;i<4;++i){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx>0&&nx<=n&&ny>0&&ny<=n&&vis[nx][ny]==false&&mp[nx][ny]==0){ dfs(nx,ny); } } } int main(){ cin>>n; for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ cin>>mp[i][j]; } } cin>>sx>>sy>>ex>>ey; if(mp[sx][sy]==1){ puts("NO"); return 0; } dfs(sx,sy); puts(fg?"YES":"NO"); return 0; }
并查集
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 10051005; int m,n,k,pre[maxn],ans; bool vis[maxn]; void init() { memset(vis,0,sizeof(vis)); for(int i=1;i<=n*m;i++) pre[i] = i; } int find(int x) { if(x!=pre[x]) return pre[x] = find(pre[x]); return x; } void join(int x,int y) { int xx = find(x); int yy = find(y); if(xx!=yy) { pre[yy] = xx; } } int main() { scanf("%d%d%d",&n,&m,&k); init(); for(int i=0;i<k;i++) { int x,y; scanf("%d%d",&x,&y); join(x,y); } for(int i=1;i<=n*m;i++) { vis[find(i)] = 1; // cout<<pre[i]<<" "<<find(i)<<endl; } for(int i=1;i<=n*m;i++) ans += vis[i]; cout<<ans<<endl; return 0; }
大数加法
7-5 a+b（正长小数版） (5 分)
给定两个正的小数a,b，求a,b之和。需要注意的是，这两个小数的有效数字位数比较多，最大有100位有效数字。
输入格式:
两行，分别表示正小数a,b。该小数一定带有小数点。
输出格式:
两者之和。如果结果小数存在末尾0，均保留。
输入样例:
0.9999999999999999999999999999999999999999999999999999999999
0.0000000000000000000000000000000000000000000000000000000001
输出样例:
1.0000000000000000000000000000000000000000000000000000000000
#include<stdio.h> #include<string.h> int search(char a[]){ int i=0; while(a[i]!='.'){ i++; } return i; } int main(){ char a[220],b[220],m[220]; int pa,pb,pc,stra,strb; int i,j,n; gets(a); gets(b); stra=strlen(a)-1; strb=strlen(b)-1; pa=search(a); pb=search(b); pc=pb; if(pa>=pb){strcpy(m,a);pc=pa;} else strcpy(m,b); int xiao=stra-pa,zeng=pa; if(pa>pb)zeng=pb; if(stra-pa>=strb-pb){ xiao=strb-pb; for(n=stra-pa;n>0;n--){ i=n+pc; j=n+pa; m[i]=a[j]; } } else for(n=strb-pb;n>0;n--){ i=n+pc; j=n+pb; m[i]=b[j]; } // printf("xiao=%dpc=%d\n",xiao,pa); //¼Ó·¨ int t=0; for(;xiao>0;xiao--){ i=pa+xiao; j=pb+xiao; n=pc+xiao; m[n]=a[i]+b[j]-'0'+t; t=0; if(m[n]>'9'){m[n]-=10;t=1;} } int k; for(k=1;k<=zeng;k++){ i=pa-k; j=pb-k; n=pc-k; m[n]=a[i]+b[j]-'0'+t; t=0; if(m[n]>'9'){m[n]-=10;t=1;} } if(t==1)for(--n;n>=0;n--){ m[n]=m[n]+t; t=0; if(m[n]>'9'){m[n]-=10;t=1;} } if(t==1&&n==-1)printf("1"); puts(m); }
标题：机器人繁殖
X星系的机器人可以自动复制自己。它们用1年的时间可以复制出2个自己，然后就失去复制能力。
每年X星系都会选出1个新出生的机器人发往太空。也就是说，如果X星系原有机器人5个，
1年后总数是：5 + 9 = 14
2年后总数是：5 + 9 + 17 = 31
如果已经探测经过n年后的机器人总数s，你能算出最初有多少机器人吗？
数据格式：
输入一行两个数字n和s，用空格分开，含义如上。n不大于100，s位数不超过50位。
要求输出一行，一个整数，表示最初有机器人多少个。
例如：
用户输入：
2 31
则程序应该输出：
5
再例如：
用户输入：
97 2218388550399401452619230609499
则程序应该输出：
8
资源约定：
峰值内存消耗 < 512M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
#include<iostream> #include<cmath> using namespace std; int main(){ //需要注意，这里可能会用到大数运算，但非常神奇的就是这里的double居然不会出错 double s; int n, k; cin >> n >> s; k = (s-n-1)/(pow(2, n+1) -1) +1; cout << k; return 0; }
从X星截获一份电码，是一些数字，如下：
13
1113
3113
132113
1113122113
....
YY博士经彻夜研究，发现了规律：
第一行的数字随便是什么，以后每一行都是对上一行“读出来”
比如第2行，是对第1行的描述，意思是：1个1，1个3，所以是：1113
第3行，意思是：3个1,1个3，所以是：3113
请你编写一个程序，可以从初始数字开始，连续进行这样的变换。
输入
第一行输入一个数字组成的串，不超过100位
第二行，一个数字n，表示需要你连续变换多少次，n不超过20
输出一个串，表示最后一次变换完的结果。
输出
输出一个串，表示最后一次变换完的结果。
样例输入
5
7
样例输出
13211321322115
#include<iostream> #include<string.h> #include<string> using namespace std; int main() { char code[10000]; memset(code, '\0', sizeof(code)); // 注意要初始化 char codetmp[10000]; memset(codetmp, '\0', sizeof(codetmp)); // 注意要初始化 int index = 0; int n; cin >> code; int len = strlen(code); cin >> n; char start; int num = 0; while (n--) // 这个while循环针对code数组 { bool flag = 0; start = code[0]; // 标记当前连续的那个字符 index = 0; num = 0; len = strlen(code); for (int i = 0; i<len; i++) { if (code[i]==start) // 如果 当前字符==当前连续字符 num++; if (i == len-1) // 如果已经是最后一个字符了 flag = 1; if (code[i]!=start) { /* 先把个数num和字符start存起来 */ codetmp[index++] = num + '0'; // codetmp是字符数组，所以要加上'0' codetmp[index++] = start; /* 再把当前连续字符换成code[i] */ start = code[i]; num = 1; } } if (flag) // 如果已经是最后一个字符，因为我们还没有存num和start，得操作如下 { codetmp[index++] = num + '0'; codetmp[index++] = start; } /* 因为要保证while循环针对code数组，这里把codetmp数组复制到code数组 */ int t_len = strlen(codetmp); for (int i = 0; i<t_len; i++) code[i] = codetmp[i]; } cout << code << endl; // system("pause"); }
题目描述
X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？
已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。
例如：
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
坦克车只能水平或垂直方向上移动到相邻的区。
输入
输入第一行是一个整数n，表示方阵的大小， 4<=n<100
接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。
A，B都只出现一次。
输出
要求输出一个整数，表示坦克从A区到B区的最少移动步数。
如果没有方案，则输出-1
样例输入
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
样例输出
10
#include <bits/stdc++.h>//万能头文件 using namespace std; char Map[101][101]; //地图数组 bool Vis[101][101]; //标记数组 标记是否走过 int Next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //方向数组 遍历方向 typedef struct node { //定义结构体数组，便于操作调用 包含坐标，步数，符号 int x, y, step; char flag; } node; node n[10001]; //BFS数组一般是m*m,再开大一点 int main() { int m; cin >> m; getchar(); //吃掉回车 int head, tail, x, y, tx, ty; for (int i = 1; i <= m; i++) { for (int j = 1; j <= m; j++) { scanf("%c", &Map[i][j]); if (Map[i][j] == 'A') { //记下起点位置的坐标 x = i, y = j; } getchar(); //吃掉空格和回车 } } head = tail = 1; //初始化 BFS可以理解为一个队列，头和尾 n[head].x = x; n[head].y = y; n[head].step = 0; n[head].flag = ' '; Vis[x][y] = 1; //标记起点位置为走过了 tail++; while (head < tail) { //BFS核心 for (int i = 0; i < 4; i++) { //遍历4个方向 tx = n[head].x + Next[i][0]; ty = n[head].y + Next[i][1]; if (tx > m || ty > m || tx < 1 || ty < 1) //出边界 continue; if (Vis[tx][ty] == 0 && n[head].flag != Map[tx][ty]) { //没走过且符合+- Vis[tx][ty] = 1; n[tail].flag = Map[tx][ty]; n[tail].x = tx; n[tail].y = ty; n[tail].step = n[head].step + 1; tail++; } } if (n[head].flag == 'B') { //走到终点 cout << n[head].step << endl; return 0; } head++; } cout << "-1"; //走不到终点 return 0; }
