POJ 1915
给定一个骑士(马)在棋盘上的起点和终点,输出需要移动的最小步数。如果起始点和终点相同,则输出 0。
BFS,向8种走位搜索,搜到就行了。
#include<stdio.h> #include<queue> using namespace std; /* 前两次wa是没有清空队列 */ struct point { int x; int y; int step; }; queue<point> r; int cb[500][500],v[500][500];//chessboard 和 标记 int dx[10]={-2,-1,1,2,2,1,-1,-2}; int dy[10]={1,2,2,1,-1,-2,-2,-1}; int main(){ int n1,n,l; int x1,y1,x2,y2; scanf("%d",&n); for(n1=0;n1<n;n1++){ scanf("%d",&l); scanf("%d %d",&x1,&y1); scanf("%d %d",&x2,&y2); for(int i=0;i<l;i++) for(int j=0;j<l;j++){ v[i][j] = 0; } point start; start.x = x1; start.y = y1; start.step = 0; r.push(start); v[start.x][start.y] = 1; //bfs while(!r.empty()){ int x = r.front().x,y = r.front().y; if(x==x2&&y==y2) { printf("%d\n",r.front().step); break; } for(int k=0;k<8;k++){ int nx,ny; nx = x + dx[k]; ny = y +dy[k]; if(nx>=0&&nx<l&&ny>=0&&ny<l&&v[nx][ny]==0){ point temp; temp.x = nx; temp.y = ny; temp.step = r.front().step +1; r.push(temp); v[nx][ny] = 1; } } r.pop(); } while(!r.empty()) r.pop(); //清空队列 } return 0; }
有两行n列的网格,每格要么是0,要么是1(0表示没障碍可以通过,1表示有障碍不可以通过。人物可以从(\(x_1,y_1\))移动到\((x_2,y_2)\),其中\(|x_1-x_2|<=1,|y_1-y_2|<=1\)。判断能不能从\((1,1)\)移动到\((2,n)\)。
如果有一列全是1,人物就无法突破1的阵列,输出NO。否则就输出YES。
#include<stdio.h> // 把字符数组写成数字数组了 int main(){ int i,n; int flag; scanf("%d",&n); for(i=0;i<n;i++){ int j,m; char a[200],b[200]; scanf("%d",&m); flag =0; getchar(); for(j=0;j<m;j++) scanf("%c",&a[j]); getchar(); for(j=0;j<m;j++) scanf("%c",&b[j]); for(j=0;j<m;j++){ if(a[j]=='1'&&b[j]=='1'){ flag = 1; printf("NO\n"); break; } } if(flag == 0) printf("YES\n"); } return 0; }
小Q正在设计一款2D卡丁车游戏,你的任务是帮助小Q实现其中的一部分功能。
在这款游戏中,游戏地图是一张 n 行 m 列的网格,从上到下依次编号为第 1 行到第 n 行,从左往右依次编号为第 1 列到第 m 列,其中第 i 行第 j 列的格子的坐标为 (i,j),每个格子要么是可以通行的平地,要么是不可通行的障碍。
在地图上的某个平地格子处有一辆由玩家操控的卡丁车。卡丁车的移动速率为 vv,并且一共有8种可能的朝向,分别为:
一开始卡丁车朝上位于某个平地格子处,其初始移动速率为 v=0。接下来玩家将依次输入 q 条操作指令,每条操作指令是下列中的一种:
在执行完每条操作指令后,卡丁车都会沿着其朝向前进 v 步,在移动结束后才会继续响应后续指令。在前进的过程中,如果某一步尝试驶入某个障碍格子或者尝试驶出地图,那么说明卡丁车发生了碰撞,它将就此结束移动,在保持朝向的同时速率 v 降低为 0。特别要注意的是,当朝向是斜45度时,为了防止"穿模"现象的发生,如果卡丁车两侧都是障碍,那么卡丁车同样将被认为发生了碰撞。例如卡丁车朝向右下,现在将从 (x,y) 移动到(x+1,y+1),那么如果 (x+1,y) 和(x,y+1) 都是障碍,则卡丁车发生了碰撞。
请写一个程序,在执行完每条操作指令后且卡丁车完成移动之后,汇报卡丁车的坐标以及这次移动过程中是否发生了碰撞。
有一个n*m的地图,每个坐标可能是"#"(障碍), "."(平地), " * "(卡丁车)中的一种。接下来有q(1<q<500)条指令,输出每条指令后车的位置和是否撞墙了。
模拟,设置一个移动和转弯的函数,依次读取命令执行即可。当速度大于1的时候,随时可能撞墙,我选择走一步看一下前面是不是墙。在向斜的方向上移动时,要判断是否穿墙,即额外判断车和下个位置形成的2*2的格子里的另外两个是不是都是墙。
我写烦了,可以搞个二维数组存八个方向的移动,然后把上下左右作一类讨论,其余方向做一类讨论。(
#include<stdio.h> char map[100][100]; //存地图 char ww[550]; //存命令 int v=0,k,k1; //0上 1右上 2右 。。。 void rush(int x,int y,int k,int d,int v){ //x y k d 方向 v 速度 if(k==0) return ; else{ if(ww[k1-k]=='U'){ v++; } else if(ww[k1-k]=='D'){ if(v>0) v--; } else if(ww[k1-k]=='R'){ d++; if(d==8) d = 0; } else if(ww[k1-k]=='L'){ d--; if(d==-1) d = 7; } int v2; int flag=0; if(v){ if(d==0){ for(v2=1;v2<=v;v2++){ if(map[x-v2][y]=='#'){ printf("Crash! %d %d\n",x-v2+1,y); rush(x-v2+1,y,k-1,0,0); flag =1; break; //****************** } } if(flag==0) { printf("%d %d\n",x-v,y); rush(x-v,y,k-1,0,v); } } else if(d==2){ for(v2=1;v2<=v;v2++){ if(map[x][y+v2]=='#'){ printf("Crash! %d %d\n",x,y+v2-1); rush(x,y+v2-1,k-1,2,0); flag =1; break; } } if(flag==0) { printf("%d %d\n",x,y+v); rush(x,y+v,k-1,2,v); } } else if(d==4){ for(v2=1;v2<=v;v2++){ if(map[x+v2][y]=='#'){ printf("Crash! %d %d\n",x+v2-1,y); rush(x+v2-1,y,k-1,4,0); flag =1; break; } } if(flag==0) { printf("%d %d\n",x+v,y); rush(x+v,y,k-1,4,v); } } else if(d==6){ for(v2=1;v2<=v;v2++){ if(map[x][y-v2]=='#'){ printf("Crash! %d %d\n",x,y-v2+1); rush(x,y-v2+1,k-1,6,0); flag =1; break; } } if(flag==0) { printf("%d %d\n",x,y-v); rush(x,y-v,k-1,6,v); } } else if(d==1){ for(v2=1;v2<=v;v2++){ if(map[x-v2][y+v2]=='#'||(map[x-v2][y+v2-1]=='#'&&map[x-v2+1][y+v2]=='#')){ printf("Crash! %d %d\n",x-v2+1,y+v2-1); rush(x-v2+1,y+v2-1,k-1,1,0); flag =1; break; } } if(flag==0) { printf("%d %d\n",x-v,y+v); rush(x-v,y+v,k-1,1,v); } } else if(d==7){ for(v2=1;v2<=v;v2++){ if(map[x-v2][y-v2]=='#'||(map[x-v2][y-v2+1]=='#'&&map[x-v2+1][y-v2]=='#')){ printf("Crash! %d %d\n",x-v2+1,y-v2+1); rush(x-v2+1,y-v2+1,k-1,7,0); flag =1; break; } } if(flag==0) { printf("%d %d\n",x-v,y-v); rush(x-v,y-v,k-1,7,v); } } else if(d==5){ for(v2=1;v2<=v;v2++){ if(map[x+v2][y-v2]=='#'||(map[x+v2][y-v2+1]=='#'&&map[x+v2-1][y-v2]=='#')){ printf("Crash! %d %d\n",x+v2-1,y-v2+1); rush(x+v2-1,y-v2+1,k-1,5,0); flag =1; break; } } if(flag==0) { printf("%d %d\n",x+v,y-v); rush(x+v,y-v,k-1,5,v); } } else if(d==3){ for(v2=1;v2<=v;v2++){ if(map[x+v2][y+v2]=='#'||(map[x+v2-1][y+v2]=='#'&&map[x+v2][y+v2-1]=='#')){ printf("Crash! %d %d\n",x+v2-1,y+v2-1); rush(x+v2-1,y+v2-1,k-1,3,0); flag =1; break; } } if(flag==0) { printf("%d %d\n",x+v,y+v); rush(x+v,y+v,k-1,3,v); } } } else{ printf("%d %d\n",x,y); rush(x,y,k-1,d,v); } } return ; } int main(){ int m,n,i,j; scanf("%d %d",&m,&n); //边界 1~m 1~n for(i=0;i<=m+1;i++){ map[i][0]='#'; map[i][n+1]='#'; } for(i=0;i<=n+1;i++){ map[0][i]='#'; map[m+1][i]='#'; } //输入 getchar(); for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ scanf("%c",&map[i][j]); } getchar(); } int x1,y1; // x1 , y1 定位 for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(map[i][j]=='*'){ x1 = i ; y1 = j ; } } } scanf("%d",&k); k1 = k; scanf("%s",ww); rush(x1,y1,k,0,0); return 0; }
输入n(0<n<16), 找出1~n组成的一个圆,要求圆上相邻的两个数之和要是素数,按1为首,一排数的格式输出。
DFS+回溯,v[20]用来标记数是否用过,每用一个数标记一下,深搜结束取消标记,达到遍历的效果
大致就是从第二个数开始n-1个数全排列过一遍,符合相邻数相加是素数且最后一个数+1也是素数就输出。
#include<stdio.h> #include<math.h> int v[20],num[20]; int isprime(int x,int y){ int z = x + y; for(int i=2;i<=sqrt(z);i++){ if(z%i==0) return 0; } return 1; } void dfs(int x,int n){ //x 代表第几个数 if(x==n&&isprime(1,num[n])){ for(int j = 1;j<n;j++) printf("%d ",num[j]); printf("%d",num[n]); printf("\n"); } else{ for(int i=2;i<=n;i++){ if(isprime(num[x],i)&&v[i]==0){ v[i] = 1; num[x+1] = i; dfs(x+1,n); v[i] = 0; } } } } int main(){ int n,k=1; num[1] = 1; while(scanf("%d",&n)!=EOF){ if(k!=1) printf("\n"); // 。。。 for(int i = 1;i<=n;i++) v[i] = 0; printf("Case %d:\n",k++); dfs(1,n); } return 0; }
在草场上有狼和羊,狼和羊相邻羊就会被吃掉,可以在草地上放狗阻挡狼吃羊,问是否能保护所有羊,能就输出一种可能性,不能就不能。
只要狼和羊不相邻,就可以一圈狗把羊/狼围住,那肯定吃不着了。为了简化输出,可以把草全换成狗。
#include<iostream> using namespace std; // L17 L18 为什么不能互换 char cc[505][505]; int main(){ int r,c; scanf("%d %d",&r,&c); int i,j,flag = 0; for(i=1;i<=r;i++){ for(j=1;j<=c;j++){ cin >> cc[i][j]; } } for(i=1;i<=r;i++){ for(j=1;j<=c;j++){ if(cc[i][j]=='S'){ if(cc[i-1][j]=='W'||cc[i+1][j]=='W'||cc[i][j-1]=='W'||cc[i][j+1]=='W') { printf("No\n"); return 0; } } } } printf("Yes\n"); for(i=1;i<=r;i++){ for(j=1;j<=c;j++){ if(cc[i][j]=='.') printf("D"); else printf("%c",cc[i][j]); } printf("\n"); } return 0; }
有n个数(n<18)形成一段序列,求连续子序列的最大乘积,都小于0就输出0
求连续子序列的最大乘积,那就遍历每一种子序列求乘积,乘积最大可到\(10^{18}\),用long long 存最大值。
#include<stdio.h> int a[20]; int main(){ long long max,temp; int N,i,j,l,t,k=0; while(scanf("%d",&N)!=EOF){ max = 0; k++; for(i=0;i<N;i++) scanf("%d",&a[i]); for(i=0;i<N;i++){ //头 for(l=1;i+l<=N;l++){ //长度 temp = 1; for(t=0;t<l;t++) temp *=a[i+t]; if(temp>max) max = temp; } } printf("Case #%d: The maximum product is %lld.\n\n",k,max); } return 0; }