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

简介:

猫和老鼠 蓝桥杯/手速/暴力练习赛
【题目描述】
 
猫和老鼠在10*10 的方格中运动,例如:
 *...*.....
 ......*...
 ...*...*..
 ..........
 ...*.C....
 *.....*...
 ...*......
 ..M......*
 ...*.*....
 .*.*......
 C=猫(CAT)
 M=老鼠(MOUSE)
 *=障碍物
 .=空地
 猫和老鼠每秒中走一格,如果在某一秒末他们在同一格中,我们称他们“相遇”。
 注意,“对穿”是不算相遇的。猫和老鼠的移动方式相同:平时沿直线走,下一步如果会走到
 障碍物上去或者出界,就用1 秒的时间做一个右转90 度。一开始他们都面向北方。
 编程计算多少秒以后他们相遇。
 
【输入格式】
 
10 行,格式如上
 
【输出格式】
 
相遇时间T。如果无解,输出-1。
 
【样例输入】
 
*...*.....
 ......*...
 ...*...*..
 ..........
 ...*.C....
 *.....*...
 ...*......
 ..M......*
 ...*.*....
 .*.*......


/*
    思路:如果猫和老鼠不相遇,那么一定是猫在某一个格子沿着某一个方向重复走了2次以上并且
    老鼠也是这样。 
*/ 
#include<iostream> 
#include<cstring> 
#include<cstdio> 
#include<algorithm>
using namespace std;

char mp[15][15];

const int left_dir = 1;
const int right_dir = 2;
const int up = 3;
const int down = 4;
const int mouse = 1;
const int cat = 0;

struct node{
    int x, y;
    int dir;
    node(){
        dir = up;
    }
    
    bool flag[15][15][5];//记录当前格子在某一个方向上是否走过 
    
    void init(int x, int y){
        memset(flag, false, sizeof(flag));
        this->x = x;
        this->y = y;
        flag[x][y][up] = true;
    }
};

node nd[2];
int cnt = 0;

bool move(int i){
    int x=nd[i].x, y=nd[i].y;
    int newdir;
    switch(nd[i].dir){
        case up:
            x-=1;
            newdir = right_dir;
            break;
        case down:
            x+=1;
            newdir = left_dir;
            break;
        case left_dir:
            y-=1;
            newdir = up;
            break;
        case right_dir:
            y+=1;
            newdir = down;
            break;
    }
    if(mp[x][y] != '*'){
        nd[i].x = x;
        nd[i].y = y;
    } else {
        nd[i].dir = newdir;
    }
    
    if(!nd[i].flag[x][y][nd[i].dir]){
        nd[i].flag[x][y][nd[i].dir] = true;
        return true;        
    } else return false;
}

void test(){
    bool flag = true, flag1=false, flag2=false;
    while(flag){
        if(nd[cat].x == nd[mouse].x && nd[cat].y == nd[mouse].y) break;
        if(!move(cat))
            flag1 = true;
        if(!move(mouse))
            flag2 = true;
        ++cnt;
        if(flag1 && flag2) flag = false;
    }
    if(flag) printf("%d\n", cnt);
    else printf("-1\n");
}

int main() {
    memset(mp, '*', sizeof(mp));
    for(int i=1; i<=10; ++i){
        scanf("%s", mp[i]+1);
        mp[i][strlen(mp[i]+1)+1] = '*';
        for(int j=1; j<=10; ++j){
            if(mp[i][j]=='C'){
                nd[cat].init(i, j);
                mp[i][j] = '.';
            }
            else if(mp[i][j] == 'M'){
                nd[mouse].init(i, j);
                mp[i][j] = '.';
            }
        }
        getchar();
    }
    test();
    return 0;
}
/*
*...*.....
......*...
...*...*..
..........
...*.C....
*.....*...
...*......
..M......*
...*.*....
.*.*......
*/


目录
相关文章
|
21天前
|
Java
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
2021蓝桥杯大赛软件类国赛Java大学B组 完全日期 复杂遍历搜索
22 2
|
1月前
|
算法 Python
蓝桥杯-搜索BFS+DFS
蓝桥杯-搜索BFS+DFS
16 2
|
21天前
|
存储 前端开发 算法
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
2016届蓝桥杯大赛软件类国赛Java大学B组 反幻方 暴力搜索
11 0
|
2月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
40 1
|
2月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
69 0
|
2月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
57 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
53 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
64 0
|
2月前
|
机器学习/深度学习 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
62 0