猫和老鼠 蓝桥杯/手速/暴力练习赛(暴力搜索)

简介:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
猫和老鼠 蓝桥杯/手速/暴力练习赛
【题目描述】
 
猫和老鼠在10*10 的方格中运动,例如:
  *...*.....
  ......*...
  ...*...*..
  ..........
  ...*.C....
  *.....*...
  ...*......
  ..M......*
  ...*.*....
  .*.*......
  C=猫(CAT)
  M=老鼠(MOUSE)
  *=障碍物
  .=空地
  猫和老鼠每秒中走一格,如果在某一秒末他们在同一格中,我们称他们“相遇”。
  注意,“对穿”是不算相遇的。猫和老鼠的移动方式相同:平时沿直线走,下一步如果会走到
  障碍物上去或者出界,就用1 秒的时间做一个右转90 度。一开始他们都面向北方。
  编程计算多少秒以后他们相遇。
 
【输入格式】
 
10 行,格式如上
 
【输出格式】
 
相遇时间T。如果无解,输出-1。
 
【样例输入】
 
*...*.....
  ......*...
  ...*...*..
  ..........
  ...*.C....
  *.....*...
  ...*......
  ..M......*
  ...*.*....
  .*.*......
复制代码
  1 /*
  2     思路:如果猫和老鼠不相遇,那么一定是猫在某一个格子沿着某一个方向重复走了2次以上并且
  3     老鼠也是这样。 
  4 */ 
  5 #include<iostream> 
  6 #include<cstring> 
  7 #include<cstdio> 
  8 #include<algorithm>
  9 using namespace std;
 10 
 11 char mp[15][15];
 12 
 13 const int left_dir = 1;
 14 const int right_dir = 2;
 15 const int up = 3;
 16 const int down = 4;
 17 const int mouse = 1;
 18 const int cat = 0;
 19 
 20 struct node{
 21     int x, y;
 22     int dir;
 23     node(){
 24         dir = up;
 25     }
 26     
 27     bool flag[15][15][5];//记录当前格子在某一个方向上是否走过 
 28     
 29     void init(int x, int y){
 30         memset(flag, false, sizeof(flag));
 31         this->x = x;
 32         this->y = y;
 33         flag[x][y][up] = true;
 34     }
 35 };
 36 
 37 node nd[2];
 38 int cnt = 0;
 39 
 40 bool move(int i){
 41     int x=nd[i].x, y=nd[i].y;
 42     int newdir;
 43     switch(nd[i].dir){
 44         case up:
 45             x-=1;
 46             newdir = right_dir;
 47             break;
 48         case down:
 49             x+=1;
 50             newdir = left_dir;
 51             break;
 52         case left_dir:
 53             y-=1;
 54             newdir = up;
 55             break;
 56         case right_dir:
 57             y+=1;
 58             newdir = down;
 59             break;
 60     }
 61     if(mp[x][y] != '*'){
 62         nd[i].x = x;
 63         nd[i].y = y;
 64     } else {
 65         nd[i].dir = newdir;
 66     }
 67     
 68     if(!nd[i].flag[x][y][nd[i].dir]){
 69         nd[i].flag[x][y][nd[i].dir] = true;
 70         return true;        
 71     } else return false;
 72 }
 73 
 74 void test(){
 75     bool flag = true, flag1=false, flag2=false;
 76     while(flag){
 77         if(nd[cat].x == nd[mouse].x && nd[cat].y == nd[mouse].y) break;
 78         if(!move(cat))
 79             flag1 = true;
 80         if(!move(mouse))
 81             flag2 = true;
 82         ++cnt;
 83         if(flag1 && flag2) flag = false;
 84     }
 85     if(flag) printf("%d\n", cnt);
 86     else printf("-1\n");
 87 }
 88 
 89 int main() {
 90     memset(mp, '*', sizeof(mp));
 91     for(int i=1; i<=10; ++i){
 92         scanf("%s", mp[i]+1);
 93         mp[i][strlen(mp[i]+1)+1] = '*';
 94         for(int j=1; j<=10; ++j){
 95             if(mp[i][j]=='C'){
 96                 nd[cat].init(i, j);
 97                 mp[i][j] = '.';
 98             }
 99             else if(mp[i][j] == 'M'){
100                 nd[mouse].init(i, j);
101                 mp[i][j] = '.';
102             }
103         }
104         getchar();
105     }
106     test();
107     return 0;
108 }
109 /*
110 *...*.....
111 ......*...
112 ...*...*..
113 ..........
114 ...*.C....
115 *.....*...
116 ...*......
117 ..M......*
118 ...*.*....
119 .*.*......
120 */









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/4415666.html,如需转载请自行联系原作者
目录
相关文章
|
25天前
|
Java
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
23 2
|
1月前
|
算法 Python
蓝桥杯-搜索BFS+DFS
蓝桥杯-搜索BFS+DFS
17 2
|
25天前
|
存储 前端开发 算法
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
12 0
|
2月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
40 1
|
2月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
71 0
|
2月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
57 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
55 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
67 0
|
2月前
|
机器学习/深度学习 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
62 0