题解 P2372 【yyy2015c01挑战算周长】

Alex_Wei · 2019-01-19 12:05:17 · 题解

主要思路：dfs（深度优先搜索）

注意点：网格中心的'X'与其边界上8个方向的'X'都是相邻的，但是算周长的时候只能算上下左右4个方向

具体思路见代码

#include<bits/stdc++.h>
using namespace std;
int m,n,x,y,ans,pd[22][22],dx[8]={-1,-1,1,1,-1,0,0,1},dy[8]={-1,1,-1,1,0,-1,1,0}; 
//pd:判断这个方格有没有被访问过，dx和dy:搜索时的方向（0-3是四个角，4-7是上下左右） 
char k[22][22];
void dfs(int a,int b)
{
    pd[a][b]=1;//标记这个方格已经被访问过 
    for(int c=0;c<8;c++){
        int d=dx[c]+a,e=dy[c]+b;
        if(d>0&&d<=m&&e>0&&pd[d][e]==0&&k[d][e]=='X')dfs(d,e);//如果这个格子没出界，没被访问过并且显示的是'X'，就访问这个格子
        if(c>3&&(d<=0||d>m||e<=0||e>n||k[d][e]!='X'))ans++;//如果方向是上下左右，并且出界了或者显示的不是'X'，周长就要+1 
    }
}
int main()
{
    cin>>m>>n>>x>>y;
    for(int a=1;a<=m;a++)
        for(int b=1;b<=n;b++)
            cin>>k[a][b];
    dfs(x,y),cout<<ans;
    return 0;
}