题目：
这是我见过的把简单问题描述的特复杂的最严重的题……给个矩阵，阵内有不等值（奶酪），两个点，每单位时间老鼠点贪心走矩阵，求猫点与老鼠点汇合最短路径
Sample Input:
2 2 15 3 2 4 0 1 3 3 1 5 9 3 7 0 2 4 6 2 0
Sample Output:
1 impossible
思路：
百思不得其解，在得知原来老鼠啃奶酪不花费时间之后，咋思都得其解……
方案：
计算出老鼠的行走路径并保存到path数组，遍历path，判断猫是否能在当前步数下走到老鼠所在格，能程序终止输出当前步数，遍历整个path均不能则impossible。
代码：
1 #include <stdio.h> 2 #include <math.h> 3 4 #define MAX 100 5 6 typedef struct Point 7 { 8 int x,y; 9 }Point; 10 11 void CatchTheMouse(int matrix[MAX][MAX],int n,int m,Point cat); 12 Point Next(int matrix[MAX][MAX],int n,int m,Point cur); 13 int Dis(Point cat,int step,Point mice); 14 15 int main() 16 { 17 int matrix[MAX][MAX]; 18 int n,m,i,j; 19 Point cat; 20 while(scanf("%d %d",&n,&m)==2) 21 { 22 memset(matrix,0,sizeof(matrix)); 23 for(i=0;i<=n-1;++i) 24 for(j=0;j<=m-1;++j) 25 scanf("%d",&matrix[i][j]); 26 scanf("%d %d",&cat.x,&cat.y); 27 CatchTheMouse(matrix,n,m,cat); 28 } 29 return 0; 30 } 31 32 void CatchTheMouse(int matrix[MAX][MAX],int n,int m,Point cat) 33 { 34 Point path[MAX*MAX]; 35 memset(path,0,sizeof(path)); 36 int len_cnt=0; 37 Point cur={0,0}; 38 Point next; 39 while((next=Next(matrix,n,m,cur)).x!=0||next.y!=0) 40 { 41 cur=next; 42 path[++len_cnt]=next; 43 } 44 45 int i; 46 for(i=1;i<=len_cnt;++i) 47 if(Dis(cat,i,path[i])==0) 48 break; 49 if(i==len_cnt+1) 50 printf("impossible\n"); 51 else 52 printf("%d\n",i); 53 } 54 55 Point Next(int matrix[MAX][MAX],int n,int m,Point cur) 56 { 57 matrix[cur.x][cur.y]=0; 58 int max=0,ahead; 59 Point ret={0,0}; 60 if(cur.x-1>=0&&matrix[cur.x-1][cur.y]>max) 61 { 62 max=matrix[cur.x-1][cur.y]; 63 ahead=0; 64 } 65 if(cur.y+1>=0&&matrix[cur.x][cur.y+1]>max) 66 { 67 max=matrix[cur.x][cur.y+1]; 68 ahead=3; 69 } 70 if(cur.x+1>=0&&matrix[cur.x+1][cur.y]>max) 71 { 72 max=matrix[cur.x+1][cur.y]; 73 ahead=6; 74 } 75 if(cur.y-1>=0&&matrix[cur.x][cur.y-1]>max) 76 { 77 max=matrix[cur.x][cur.y-1]; 78 ahead=9; 79 } 80 if(max==0) 81 return ret; 82 ret=cur; 83 switch(ahead) 84 { 85 case 0: 86 --ret.x; 87 break; 88 case 3: 89 ++ret.y; 90 break; 91 case 6: 92 ++ret.x; 93 break; 94 case 9: 95 --ret.y; 96 break; 97 } 98 return ret; 99 } 100 101 int Dis(Point cat,int step,Point mice) 102 { 103 if(abs(cat.x-mice.x)+abs(cat.y-mice.y)<=step) 104 return 0; 105 else 106 return 1; 107 }
心得：
今后一定要记得精简代码，这么简单个题干出去一百行……