为什么每次刷题的时候,我都觉得我学的算法知识是在梦里学的呜呜呜。
下面是今天做的几道简单的搜索题目,很基础,都是大佬可以手撕那种,哎我还是慢慢练叭。

BFS-1 很经典的 Catch That Cow


题目大意:
数轴上农夫和牛的位置,牛不动,农夫有(x+1),(x-1),(2*x)三种走法,问能否抓到
解题思路:
将位置和步数放到队列中,如果队列非空则尝试三种方法可行否,位置到达则直接输出步数。

代码在此

#include <iostream>
#include <queue>
#include <string.h>
#define MaxSize 100010
using namespace std;

int n,k,ans;

//位置,步数 
typedef pair<int,int> p;
queue<p> que;
int visit[MaxSize];

//判断是否在可行 
bool is_in(int a){
    return a <= 100000 && a >= 0 && !visit[a]; 
}

void bfs(int x,int step){
    que.push(p(x,0));
    
    while(!que.empty()){
        if(que.front().first == k) {
            //找到的就是最短步数了!不能像DFS一样 min(step,ans) 
            cout<<que.front().second;
            break;
        }
        
        if(is_in(que.front().first + 1)){
            que.push(p(que.front().first+1, que.front().second+1));
            visit[que.front().first + 1] = 1;
        }
        
        if(is_in(que.front().first - 1)){
            que.push(p(que.front().first - 1, que.front().second + 1));
            visit[que.front().first - 1] = 1;
        }
        
        if(is_in(que.front().first * 2)){
            que.push(p(que.front().first * 2, que.front().second + 1));
            visit[que.front().first * 2] = 1;
        }
        que.pop();
    }
    return ; 
}

int main()
{
    cin>>n>>k;
    memset(visit,0,sizeof(visit));
    visit[n] = 1;
    bfs(n,0);
    return 0;
}

BFS-2 迷宫问题(BFS+记录)


题目大意:
从一点有四个方向,求从起点到终点的路径
思路:
类似上一题,特别在是二维,同时记录路径
这样关键在于可以用包含位置x,y和前序位置信息的px,py以及点的信息的结构体,整体放进队列中。
输出时要找到他的前序位置的前序..直到起始点。

代码在此

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

//本题中已确定起点终点 
int xs = 0,ys = 0,xe = 4,ye = 4;

struct p{
    int px,py;        //标记前一个点 
    int first,second;
    bool val;
};
queue<p> que;
p maze[5][5];
bool visit[5][5];

int s[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

bool is_ok(int a,int b){
    return a>=0 && a<=4 && b>=0 && b<=4 && !maze[a][b].val;
}

//逆序输出直到起点 
void prnt(int x,int y){        
    if(x == xs && y == ys) {
        printf("(%d, %d)\n",x,y);
        return;
    }
    prnt(maze[x][y].px,maze[x][y].py);
    printf("(%d, %d)\n",x,y);
    return;
}

void bfs(int x,int y){
    que.push(maze[x][y]);
    
    while(!que.empty()){
        for(int i = 0;i < 4;i++){
            int tmpx = que.front().first + s[i][0];
            int tmpy = que.front().second + s[i][1];
            
            if(!is_ok(tmpx,tmpy)) continue;
            
            if(!visit[tmpx][tmpy]){
                maze[tmpx][tmpy].px = que.front().first;
                maze[tmpx][tmpy].py = que.front().second;
                visit[tmpx][tmpy] = 1;
                que.push(maze[tmpx][tmpy]);
            }
            
            if(tmpx == xe && tmpy == ye){
                prnt(tmpx,tmpy);
                return;
            }
        }
        que.pop();
    }
} 

int main()
{
    for(int i = 0;i < 5;i++){
        for(int j = 0;j < 5;j++){
            cin>>maze[i][j].val;
            maze[i][j].first = i;
            maze[i][j].second = j;
        }
    }
    memset(visit,false,sizeof(visit));
    
    visit[xs][ys] = 1;
    bfs(xs,ys);
    return 0;
}

BFS-3 求连通块 BFS & DFS


题目大意:
给一块油田,每块于八个方向关联,求有几块连通图。
思路:
比上一道题简单,几乎一样还不用记录。就时走到一块油田后就BFS,访问后要记得变成墙。
用BFS和昨天学的DFS都写一遍。

BFS代码在此

#include <iostream>
#include <string.h>
#include <queue>
#define MaxSize 101
using namespace std;

int X,Y,ans;
char oil[MaxSize][MaxSize];
typedef pair<int,int> p;
queue<p> que;
int s[8][2] = {{1,0},{-1,0},{1,1},{-1,-1},{0,1},{0,-1},{1,-1},{-1,1}};

bool is_ok(int a,int b){
    return a >= 0 && a < X && b >= 0 && b < Y && oil[a][b] == '@';
}

void bfs(int x,int y){
    que.push(p(x,y));
    while(!que.empty()){
        for(int i = 0;i < 8;i++){
            //一定是在队头的基础上8方向 
            int tmpx = que.front().first + s[i][0];
            int tmpy = que.front().second + s[i][1];
            
            if(is_ok(tmpx,tmpy)) {
                que.push(p(tmpx,tmpy));
                oil[tmpx][tmpy] = '*'; 
            } 
        }
        que.pop();
    }
    return;
}

int main()
{
    while(cin>>X>>Y && X && Y){
        for(int i = 0;i < X;i++){
            for(int j = 0;j < Y;j++){
                cin>>oil[i][j];
            }
        }
        ans = 0;
        for(int i = 0;i < X;i++){
            for(int j = 0;j < Y;j++){
                if(oil[i][j]=='@'){
                    ans++;
                    oil[i][j] = '*';
                    bfs(i,j);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

DFS代码在此

#include <iostream>
#include <string.h>
#define MaxSize 101
using namespace std;

int X,Y,ans;
char oil[MaxSize][MaxSize];

int s[8][2] = {{1,0},{-1,0},{1,1},{-1,-1},{0,1},{0,-1},{1,-1},{-1,1}};

bool is_ok(int a,int b){
    return a >= 0 && a < X && b >= 0 && b < Y && oil[a][b] == '@';
}

void dfs(int x,int y){
    for(int j = 0;j < 8;j++){
        int tmpx = x + s[j][0];
        int tmpy = y + s[j][1];
                
        if(is_ok(tmpx,tmpy)){
            oil[tmpx][tmpy] = '*';
            dfs(tmpx,tmpy); 
        }
    }
    return;
}

int main()
{
    while(cin>>X>>Y && X && Y){
        for(int i = 0;i < X;i++){
            for(int j = 0;j < Y;j++){
                cin>>oil[i][j];
            }
        }
        ans = 0;
        for(int i = 0;i < X;i++){
            for(int j = 0;j < Y;j++){
                if(oil[i][j]=='@'){
                    ans++;
                    dfs(i,j);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

明天还要加油!虽然脑子笨 ,但是刷题总是有效果的!哼

Last modification:June 23rd, 2020 at 07:49 pm
请赏我杯奶茶,让我快乐长肉