填涂颜色

P1162 填涂颜色

哎,这道题从3月份学广搜开始就困扰我,做了2个月都没做对,一直拖到5月学动态规划,索性放下不管!

今天深搜一遍过……

主要思路:四个边缘进行搜索就可以了。

填涂颜色
#include<bits/stdc++.h>
using namespace std;
int n,mp[35][35],dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1},u,v;
void dfs(int x,int y)
{
    mp[x][y]=-1;
    for(int i=0; i<4; i++)
    {
        u=x+dx[i],v=y+dy[i];
        if(!mp[u][v])dfs(u,v);
    }
}
int main()
{
    for(int i=0; i<35; i++)
        for(int j=0; j<35; j++)
            mp[i][j]=1;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            scanf("%d",&mp[i][j]);
    for(int i=1; i<=n; i++)if(!mp[1][i])dfs(1,i);
    for(int i=1; i<=n; i++)if(!mp[n][i])dfs(n,i);
    for(int i=1; i<=n; i++)if(!mp[i][1])dfs(i,1);
    for(int i=1; i<=n; i++)if(!mp[i][n])dfs(i,n);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            if(mp[i][j]==0)mp[i][j]=2;
            if(mp[i][j]==-1)mp[i][j]=0;
        }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            printf("%d ",mp[i][j]);
        cout<<endl;
    }
    return 0;
}
AC

 

上一篇:原生JS实现简易计算器


下一篇:顺时针打印矩阵