Information
- ID
- 184
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 157
- Accepted
- 31
- Uploaded By
1.首结点入队列并标记
2.搜寻首结点的上,下,左,右结点,满足条件就入队列并标记
3.首结点出队列,下一个结点成为首节点,计数器加一
4.重复2,3步骤,直到队列中全部的结点出队列
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int n, m, x, y, ans, cnt = 0;
const int maxn = 1005;
int area[maxn][maxn];
int X[4] = {-1, 1, 0, 0}; //上下左右四个方向
int Y[4] = {0, 0, -1, 1};
bool F[maxn][maxn] = {false};
struct node {
int x;
int y;
}Node, top;
bool judge(int x, int y) {
if(x < 0 || y < 0 || x >= n || y >= m) //越界不入队列
return false;
if(F[x][y] == true || area[x][y] == 0) //被选过了或者没有树不入队列
return false;
return true;
}
void BFS(int x, int y) {
queue<node> q;
Node.x = x;
Node.y = y;
q.push(Node);
while (!q.empty()) {
top = q.front();
int lx = top.x;
int ly = top.y;
for (int i = 0; i < 4; i++) {
if (judge(lx + X[i], ly + Y[i]))
{
Node.x = lx + X[i];
Node.y = ly + Y[i];
q.push(Node);
F[Node.x][Node.y] = true;
}
}
ans++;
F[lx][ly] = true;
q.pop();
}
}
int main() {
cin >> n >> m >> x >> y;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j++) {
cin >> area[i][j];
if (area[i][j] == 1) cnt++;
}
}
if (area[x][y] == 1) {
BFS(x, y);
}
cout << ans << endl;
double rate = (double)ans / cnt;
if (rate >= 0.2)
cout << "获得成就:生 态 灭 绝 者";
else if (rate >= 0.1)
cout << "获得成就:伐伐伐伐伐木工";
else
cout <<"获得成就:就这?";
return 0;
}
#include<stdio.h>
#include<iostream>
using namespace std;
const int N=1005;
int n,m,k,fx,fy,ex,ey,sx,sy,ans,sum;
double rate;
int ma[N][N],mas[N][N];
int opx[5]={1,-1,0,0};
int opy[5]={0,0,-1,1};
void dfs(int x,int y)
{
int nx,ny;
for(int i=0;i<4;i++)
{
nx=x+opx[i];
ny=y+opy[i];
if(nx>=0&&nx<=n-1&&ny>=0&&ny<=m-1&&mas[nx][ny]==0&&ma[nx][ny]==1)
{
ans++;
mas[nx][ny]=1;
dfs(nx,ny);
}
}
}
int main()
{
scanf("%d %d",&n,&m);
scanf("%d %d",&sx,&sy);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&ma[i][j]);
if(ma[i][j]==1) sum++;
}
}
if(ma[sx][sy]==1)
{
ans++;
mas[sx][sy]=1;
dfs(sx,sy);
}
rate=(double)ans/sum;
if(rate>=0.2)
{
printf("%d\n",ans);
printf("获得成就:生 态 灭 绝 者\n");
}
else if(rate<0.2&&rate>=0.1)
{
printf("%d\n",ans);
printf("获得成就:伐伐伐伐伐木工\n");
}
else
{
printf("%d\n",ans);
printf("获得成就:就这?\n");
}
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.