试题 算法提高 Cat And Mouse
资源限制
时间限制:1.0s 内存限制:256.0MB
猫和老鼠在10×10的方格中运动(如图3-6),例如:
*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......
C=猫(CAT)
M=老鼠(MOUSE)
*=障碍物
.=空地
猫和老鼠每秒中走一格,如果在某一秒末它们在同一格中,我们称它们“相遇”。
注意:“对穿”是不算相遇的。猫和老鼠的移动方式相同:平时沿直线走,下一步如果会走到障碍物上去或者出界,就用1秒的时间做一个右转90°。一开始它们都面向北方。
编程计算多少秒以后他们相遇。
一道简单的模拟题,关键在于猫和老鼠是独立的个体,只要处理好每一秒内各自的动作即可实现。
代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
int* change(int direction, int old_x, int old_y){ // 依据前进方向进行移动
/*
direction:0:北,1:东,2:南,3:西
*/
int* new_loc = (int*)malloc(sizeof(int)*2);
switch(direction){
case 0:
new_loc[0] = old_x - 1;
new_loc[1] = old_y;
break;
case 1:
new_loc[0] = old_x;
new_loc[1] = old_y + 1;
break;
case 2:
new_loc[0] = old_x + 1;
new_loc[1] = old_y;
break;
case 3:
new_loc[0] = old_x;
new_loc[1] = old_y - 1;
break;
}
return new_loc;
}
void catMouseGame(char** graph, int cx, int cy, int cd, int mx, int my, int md, int count){
/*
参数说明:
graph:地图(输入的二维数组)
cx:老鼠所在位置的x轴坐标
cy:老鼠所在位置的y轴坐标
cd:老鼠当前的前进方向
mx:猫所在位置的x轴坐标
my:猫所在位置的y轴坐标
md:猫当前的前进方向
count:当前的秒数
*/
if(cx == mx && cy == my){ // 如果两者坐标相同,即为结束
printf("%d", count);
return;
}
/* 处理老鼠的位置 */
int* new_loc = change(md, mx, my); // 获取这一秒内的老鼠位置
int m_x = new_loc[0], m_y = new_loc[1];
if(m_x == 10 || m_y == 10 || m_x == -1 || m_y == -1 || graph[m_x][m_y] == '*'){
// 如果越界或者碰到障碍物,则改变方向,即旋转90度
md = (md+1) % 4;
m_x = mx;
m_y = my;
}
/* 处理猫的位置 */
new_loc = change(cd, cx, cy); // 获取这一秒内的猫位置
int c_x = new_loc[0], c_y = new_loc[1];
if(c_x == 10 || c_y == 10 || c_x == -1 || c_y == -1 || graph[c_x][c_y] == '*'){
// 如果越界或者碰到障碍物,则改变方向,即旋转90度
cd = (cd+1) % 4;
c_x = cx;
c_y = cy;
}
/* 开始移动 */
catMouseGame(graph, c_x, c_y, cd, m_x, m_y, md, count+1);
}
int main(){
char** graph = (char**)malloc(sizeof(char*)*10);
int i = 0;
for(i = 0; i < 10; i++){
graph[i] = (char*)malloc(sizeof(char)*10);
scanf("%s", graph[i]);
}
catMouseGame(graph, 4, 5, 0, 7, 2, 0, 0);
return 0;
}