题解 P1162 【填涂颜色】

· · 题解

题目本身比较简单，但是就是训练广度搜索的

麻烦是找第一个圈内点， 有很多种办法可以找到它。这里采用的是按照行来搜索，每行找到第一个边界点，如果这个边界点右侧的是0，那么右侧点就是内部点，否则就找下一行。

找到之后就把他放到自定的队列queue当中 而后启动先广搜索bfs算法，算法没有太多的解释，就是如果队里空了，表示完成任务调用writeDate函数输出就好；如果队列不空，就从队列尾巴取出一个点，填上2，再把它四周的数值是0的加回到队列当中去。重复这个队列操作过程就好。

ps 这种操作下已经不是队列而是堆栈了（因为是后入先出了）；如果是队列先入先出，就需要增加标记结构以避免同一个位置被多次加入队列。

代码如下：

#include <iostream>
using namespace std;
const int  MaxSize = 32;
int map[30][30];

struct POS {
    int x;
    int y;
} queue[MaxSize*MaxSize]; 
int head=0, tail=0;

int N=0;
void readDate() 
{
    cin >> N;
    for (int i=0; i<N; i++) 
    {
        for (int j=0; j<N; j++) 
        {
            cin >> map[i][j];
        }
    }
}
void writeDate(){
    for (int i=0; i<N; i++) 
    {
        for (int j=0; j<N; j++) cout << map[i][j]  << " " ;
        cout<<endl;
    }
}
void findFirst()
{
    for (int x=1; x<N-1; x++) {
        for (int y=0; y<N; y++) {
            if ( map[x][y]==0) continue;
            if ( y<N-1  && map[x][y+1] == 0 ) {
                queue[tail].x = x;
                queue[tail].y = y+1;
                tail ++;
                return;
            } else {
                break; // next line
            }
        }
    }
}
void bfs() {
    findFirst();
    while ( tail != head ) {
        int x = queue[tail-1].x;
        int y = queue[tail-1].y;
        tail--;
        map[x][y]=2;
        if ( y<N-1 && map[x][y+1] == 0 ) {
            queue[tail].x = x;
            queue[tail].y = y+1;
            tail ++;
        };
        if ( y>0 && map[x][y-1] == 0 ) {
            queue[tail].x = x;
            queue[tail].y = y-1;
            tail ++;
        };
        if ( x>=0 && map[x-1][y]==0 ) {
            queue[tail].x = x-1;
            queue[tail].y = y;
            tail ++;
        };
        if ( x<N-1 && map[x+1][y] ==0 ) {
            queue[tail].x = x+1;
            queue[tail].y = y;
            tail ++;
        }
    };
    writeDate();
}
int main(int argc, char** argv) {
    readDate();
    bfs();
    return 0;
};