【搜索】L国的战斗之伞兵

伞兵?SB?嘿嘿嘿
原题传送门

思路

这道题需要采用倒退的思想。

如果a[x][y]无风或可吹至无风区:
那么它南面如果是北风区,则北风区就也是无风或可吹至无风区(实际上就是可吹至无风区)。
那么它北面如果是南风区,则北南区就也是无风或可吹至无风区(实际上就是可吹至无风区)。
那么它东面如果是西风区,则北西区就也是无风或可吹至无风区(实际上就是可吹至无风区)。
那么它西面如果是东风区,则北东区就也是无风或可吹至无风区(实际上就是可吹至无风区)。
然后从发现是无风或可吹至无风区继续推下去,若没有则返回上一步,查看下一个可能。

这是什么思路呢?对了,这就是明显的深搜。
将无风或可吹至无风区称为安全区。
搜索安全区附近的每一个附近区域,若为安全区则继续搜索,最后统计安全区的个数即可。
另外,搜索本身会超出数组范围一格,因此要在地图四周空出一圈,我采用的方式是从数组下标1开始使用,数组尾下标多开一位。

接下来就是毫无难度的水代码了

Code

#include<iostream>
#include<cstdio>

using namespace std;

char a[1002][1002];
int n,m,ans,b[1002][1002];

void find(int i,int j)   //推路径
{  
    b[i][j]=true; //将这点记为true
    if(a[i+1][j]=='u') find(i+1,j);
    if(a[i-1][j]=='d') find(i-1,j);
    if(a[i][j+1]=='l') find(i,j+1);
    if(a[i][j-1]=='r') find(i,j-1);
}

int main()
{
    //初始化
    
    //读入
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    		cin>>a[i][j];
    //装叉走起
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    		if(a[i][j]=='o')
    			find(i,j);
    
    //输出
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    		if(b[i][j])
    			ans++;
    cout<<ans;
    return 0;
}
原文地址:https://www.cnblogs.com/gongdakai/p/11156711.html