搜索模拟版！！！（自创）

大家好，我最近发现一种模拟搜索的办法，向大家分享一下。

比如以下面的题目为例子：

描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入描述

输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1. .：黑色的瓷砖；
2. #：红色的瓷砖；
3. @：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

数据范围：

1≤W,H≤20

输出描述

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

用例输入 1

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

用例输出 1

45

思路：

1.输入部分：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int w,h;
    while (cin>>w>>h)
    {
        if (w==0 && h==0) break;
        char li[h+2][w+2];
        for (int i=0;i<=h+1;i++)
        {
            for (int j=0;j<=w+1;j++) 
            {
                li[i][j]=' ';
            }
        }
        int x1,y1,count=0;
        for (int i=1;i<=h;i++)
        {
            for (int j=1;j<=w;j++) 
            {
                cin>>li[i][j];
                if (li[i][j]=='@') x1=i,y1=j;
            }
        }
    }
}

2.向四周扩展：

        for (int i=y1+1;i<=h;i++)
        {
            if (li[x1][i]=='.') li[x1][i]='%';
            else break;
        }
        for (int i=x1+1;i<=w;i++)
        {
            if (li[i][y1]=='.') li[i][y1]='%';
            else break;
        }        
        for (int i=y1-1;i>=0;i--)
        {
            if (li[x1][i]=='.') li[x1][i]='%';
            else break;
        }
        for (int i=x1-1;i>=0;i--)
        {
            if (li[i][y1]=='.') li[i][y1]='%';
            else break;
        }

变成一个“十”字形

3.遍历

如果这个点周围4个方向有被标记的点，那么这个点就可以达到

        for (int i=0;i<w*h;i++)
        {
            for (int x=1;x<=h;x++)
            {
                for (int y=1;y<=w;y++)
                {
                    if ((li[x+1][y]=='%' || li[x-1][y]=='%' || li[x][y+1]=='%' || li[x][y-1]=='%') && li[x][y]=='.') li[x][y]='%';
                }
            }
        }

4.统计

统计被标记的砖块个数

        for (int i=1;i<=h;i++)
        {
            for (int j=1;j<=w;j++) 
            {
                if (li[i][j]=='%') count++;
            }
        } 
        cout<<count+1<<endl;

完整AC代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int w,h;
    while (cin>>w>>h)
    {
        if (w==0 && h==0) break;
        char li[h+2][w+2];
        for (int i=0;i<=h+1;i++)
        {
            for (int j=0;j<=w+1;j++) 
            {
                li[i][j]=' ';
            }
        }
        int x1,y1,count=0;
        for (int i=1;i<=h;i++)
        {
            for (int j=1;j<=w;j++) 
            {
                cin>>li[i][j];
                if (li[i][j]=='@') x1=i,y1=j;
            }
        }
        for (int i=y1+1;i<=h;i++)
        {
            if (li[x1][i]=='.') li[x1][i]='%';
            else break;
        }
        for (int i=x1+1;i<=w;i++)
        {
            if (li[i][y1]=='.') li[i][y1]='%';
            else break;
        }        
        for (int i=y1-1;i>=0;i--)
        {
            if (li[x1][i]=='.') li[x1][i]='%';
            else break;
        }
        for (int i=x1-1;i>=0;i--)
        {
            if (li[i][y1]=='.') li[i][y1]='%';
            else break;
        }
        for (int i=0;i<w*h;i++)
        {
            for (int x=1;x<=h;x++)
            {
                for (int y=1;y<=w;y++)
                {
                    if ((li[x+1][y]=='%' || li[x-1][y]=='%' || li[x][y+1]=='%' || li[x][y-1]=='%') && li[x][y]=='.') li[x][y]='%';
                }
            }
        }
        for (int i=1;i<=h;i++)
        {
            for (int j=1;j<=w;j++) 
            {
                if (li[i][j]=='%') count++;
            }
        } 
        cout<<count+1<<endl;
    }
}

缺点：效率慢