首页 > 其他分享 >hdu 1312 Red and Black (BFS模板题)

hdu 1312 Red and Black (BFS模板题)

时间:2024-02-03 18:11:06浏览次数:35  
标签:hdu hy 1312 int BFS start dx

Problem - 1312 (hdu.edu.cn)

BFS模板题

#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int wx,hy,num;
char room[25][25];
#define CHECK(x,y) (x>=0&&x<wx&&y>=0&&y<hy)
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct node{int x,y;};
void BFS(int dx,int dy){
    num=1;
    queue<node> q;
    node start,next;
    start.x=dx;
    start.y=dy;
    q.push(start);
    while(!q.empty()){
        start=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            if(CHECK(next.x,next.y)&&room[next.x][next.y]=='.'){
                room[next.x][next.y]='#';
                num++;
                q.push(next);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int x,y,dx,dy;
    while(cin>>wx>>hy){
        if(wx==0&&hy==0) break;
        for(y=0;y<hy;y++){
            for(x=0;x<wx;x++){
                cin>>room[x][y];
                if(room[x][y]=='@'){
                    dx=x;
                    dy=y;
                }
            }
        }
        num=0;
        BFS(dx,dy);
        cout<<num<<endl;
    }
    return 0;
}

 

标签:hdu,hy,1312,int,BFS,start,dx
From: https://www.cnblogs.com/accbulb/p/18005025

相关文章

  • hdu1240 Asteroids! (三维BFS)
    Problem-1240(hdu.edu.cn)三维的BFS,存在一个坐标点的变换,即输入的是(y,z,x),进行转换即可#include<iostream>#include<queue>#include<cstring>usingnamespacestd;intn,x1,y1,z1,x2,y2,z2,flag,vis[20][20][20];charroom[20][20][20];structnode{int......
  • Poj 3414 Pots (BFS+回溯+队列)
    这道题需要输出最后结果的执行过程,可以通过结构体,在结构体中定义一个数组s,s中存储了每一步的执行过程,实现了回溯。并且在运行中可以适当剪枝,减少枚举次数。 #include<iostream>#include<queue>#include<cstring>usingnamespacestd;constintN=110;intaa,bb,cc,vis[N......
  • Poj 3278 Catch That Cow (BFS+队列)
    #include<iostream>#include<queue>#include<cstring>usingnamespacestd;constintN=1e5+10;intn,k,line[N],way;structnode{intloc,step;};queue<node>q;voidBFS(intn,intk){while(!q.empty())q.pop();nodestart,next......
  • Poj3126 Prime Path (BFS+筛素数)
    #include<iostream>#include<queue>#include<cstring>constintN=10010;intt,aa,bb,prime[N],vis[N],step[N];usingnamespacestd;voidprime_(){//埃式筛法prime[0]=prime[1]=1;for(inti=2;i<10000;i++){if(prime[i])contin......
  • 状压+BFS
    洛谷2622思路定义一个结构体节点,分别存储状态和步骤,状态的某一位是1表示灯开着,是0则表示该灯关,当状态为0000时输出的步骤即为最小步骤。点击查看代码#include<bits/stdc++.h>usingnamespacestd;//#defineintlonglong#definelllonglonginta[120][102]={0};int......
  • leetcode--98. 验证二叉搜索树(bfs)
    记录13:502024-1-28https://leetcode.cn/problems/validate-binary-search-tree/想岔方向了,想的太复杂了。首先思路是每个root节点必须大于左子树的最大节点,小于右边子树的最小节点。我的做法是记录下叶子节点,因为左边叶子节点的集合(vector)的最后一个节点为左子树的最大值......
  • HDU 1175 连连看 (DFS)
    HDU1175连连看(DFS)题目:给出连连看棋盘,然后有q次询问,每次询问4个数(x1,y1,x2,y2),输出是否能不绕外面且转折不超过两次消除,输出YES/NOSampleInput34123400004321411341124113321243401430241000021124132300Sampl......
  • POJ2627 数独 (dfs or bfs)
    POJ2627数独(dfsorbfs)给出一个数独,空白用0表示,输出一个合理答案即可;SampleInput1103000509002109400000704000300502006060000050700803004000401000009205800804000107SampleOutput1436285795721394689867542313915427864689173527258639142374816956......
  • HDU2966 In case of failure 题解
    QuestionHDU2966Incaseoffailure给出平面上\(n\)个点坐标,求每个点最近的点的欧几里得距离的平方Solution算是一道K-D树的板子题维度\(K=2\)建立\(K-D\)树,在每一层更新当前最小答案\(now\_ans\),如果在然后继续遍历当前维度下距离\(\le\)的区块随机数据时间复......
  • 搜索学习笔记+杂题 (进阶二 dfs/bfs的进阶)
    前言:由于搜索的题还是做的太少了,所以以后有可能会不定期更新。四、还是进阶的dfs/bfs相关题单:戳我1、dfs(1)meetinthemiddleP2962[USACO09NOV]LightsG颠覆了我对折半搜索的认知,果然,只要满足了折半搜索的几个性质,基本上都可以使用折半搜索来处理。首先我们拿到的是一张......