codevs 2806_紅與黑_bfs

2019-11-11 04:50:12

字體：大中小

來源：轉載

供稿：網友

題目描述

有一個矩形房間，覆蓋正方形瓷磚。每塊瓷磚涂成了紅色或黑色。一名男子站在黑色的瓷磚上，由此出發，可以移到四個相鄰瓷磚之一，但他不能移動到紅磚上，只能移動到黑磚上。編寫一個程序，計算他通過重復上述移動所能經過的黑磚數。

思路

暴力搜索就可以了 O(nm)

#include <stdio.h>#include <queue>#include <cstring>#include <string>using namespace std;int a[101][101],x,y;int f[101][101],ans=0;int dx[5]={0,1,0,-1,0};int dy[5]={0,0,1,0,-1};int n,m;int bfs(){ queue<int> tx; queue<int> ty; tx.push(x); ty.push(y); while (!tx.empty()) { int xx=tx.front(),yy=ty.front(); tx.pop(); ty.pop(); for (int i=1;i<=4;i++) if (dx[i]+xx>=1&&dx[i]+xx<=n&&dy[i]+yy>=1&&dy[i]+yy<=m&&a[dx[i]+xx][dy[i]+yy]==0&&f[dx[i]+xx][dy[i]+yy]==0) { f[dx[i]+xx][dy[i]+yy]=1; ans++; tx.push(dx[i]+xx); ty.push(dy[i]+yy); } } }int main(){ scanf("%d%d",&m,&n); while (n!=0) { for (int i=1;i<=100;i++) for (int j=1;j<=100;j++) { a[i][j]=f[i][j]=0; } for (int i=1;i<=n;i++) { char ch[100]; scanf("%s",&ch); for (int j=1;j<=m;j++) { if (ch[j-1]=='#') a[i][j]=1; if (ch[j-1]=='@') { x=i; y=j; f[i][j]=1; } } } ans=1; bfs();