历年ACM

A

#include \#include \#include \#include \

#define N 26 #define M 100

//两种情况进行区别，循环调用的情况 struct data { char ch; int num; }d[N]; int f[N];

char str[M][4];

int number(char c,int n,int m,int &k) { int count,r=0; int i; if(k>n)

{//循环多次出不来 d[c-64].num=-1; f[c-64]=1; return -1; }

for(i=1;i<=m;i++) { if(str[i][0]==c && f[c-64]==0) { count=0; if(f[str[i][2]-64]==0) { k++; r=number(str[i][2],n,m,k); } else

{ r=d[str[i][2]-64].num; } if(r==-1) { d[c-64].num=-1; f[c-64]=1;

return -1;}

else{ count=count+r+1；} if(count > d[c-64].num)

{ d[c-64].num=count;} } } f[c-64]=1; return d[c-64].num; } void sort(struct data d[],int n) { int r,s; struct data dk; for(r=1;r<=n-1;r++) { for(s=r;s<=n;s++) { if(d[r].num>n>>m; while(n!=0||m!=0) { k=0;

for(i=1;i<=n;i++) { d[i].ch=i+64; d[i].num=0; f[i]=0; } for(i=1;i<=m;i++) {gets(str[i]); }

number(str[1][0],n,m,k); cout<<\ for(i=1;i<=n;i++) { if(f[i]==0) { k=0; number(d[i].ch,n,m,k); } } sort(d,n); if(d[n].num==-1) { cout<<\ } else if(m < n-1)

{cout<<\ else { for(i=1;i

cout<<\ break; } } if(i==n) { cout<<\ for(j=1;j>n>>m; } // system(\

2009年ACM

Dr.Kong的机器人

Dr.Kong设计了一个可以前进或后退机器人，该机器人在每个位置i会得到一个移动步数的指令Ki (i=1,2…N),聪明的机器人自己会判断是要前进Ki步还是后退Ki步。

例如：给定指令序列(3 3 1 2 5)，表示机器人在第1个位置时，可以前进3步到第4个位置，此时后退是不起作用的，出界；机器人在第2个位置时，可以前进3步到第5个位置，此时后退是不起作用的，出界；机器人在第3个位置时，可以前进1步到第4个位置，也可以后退1步到第2个位置等等。

你认为，对给定的两个位置A,B, 聪明的机器人从A位置走到B位置至少要判断几次？ 【标准输入】

第一行: M 表示以下有M组测试数据（0

头一行：N A B ( 1≤ N≤ 50, 1≤A,B ≤N ) 下一行: K1 K2…..Kn ( 0<=Ki<=N ) 【标准输出】

输出有M行，第i行为第i组测试数据的最少判断次数, 若无法到达，则输出-1。 【 样 例 】 标准输入 2 5 1 5 3 3 1 2 5 8 5 3 1 2 1 5 3 1 1 1 标准输出 3 -1 #include int N,A,B; int a[9][50];

int b[9][100]={0};//存放中间状态 int M,flag[100]; int w;

int lookup(int k,int i,int j) { int c=1; if(i==j) return w; if(((b[k][c]=i+a[k][i])<=N)&&(flag[i]==0)) { flag[i]=1; w=w+1; lookup(k,b[k][c],j); } else if (((b[k][c]=i-a[k][i])>=1)&&(flag[i]==0)) { flag[i]=1;