洛谷 p1141 01迷宫题解

很长时间没发博客了,今天水一下

很多dalao说染色(普通的)过不了,

我怎么就过了

其实我也是今天才知道什么是染色(由@你听风在吼 dalao指导)

然后自己打了一个,也不知道叫不叫染色,反正是过了

QAQ

这个类似连通块,我们把一整个连通块进行整体标记,每次不管访问哪一个成员,都可以直接输出已经存好的

不多说废话,上代码

#include<bits/stdc++.h>

using namespace std;

int b[1001][1001],c[1001];//b是标记哪个点是属于哪个染色区,c是每个染色区的连通块个数

char a[1001][1001];//a是矩阵

int xx[5] = {0,1,-1,0,0},yy[5] = {0,0,0,1,-1};

int n,m,tot,ku = 1;//tot是统计连通块的,ku是染色区的"名称"

void ss(int x,int y){

	tot ++;

	for(int i = 1;i <= 4;i++){

		int x2 = x + xx[i],y2 = y + yy[i];

		if(a[x][y] != a[x2][y2] && b[x2][y2] == 0 && x2 <= n && x2 > 0 && y2 <= n && y2 > 0 ){//这里要注意,染过的就不能再染了,想想为什么

			b[x2][y2] = ku;//染色

			ss(x2,y2);

		}

	}

	return;

}

int main(int argc, char const *argv[])

{

	cin>>n>>m;

    for(int i = 1;i <= n;++i) scanf("%s",a[i]+1);

    for (int i = 1; i <= n; ++i)

    {

    	for(int j = 1;j <= n;++j){

    		if(b[i][j] == 0){

    			b[i][j] = ku;//起点也要染色

    			ss(i,j);

    			c[ku] = tot;

    			tot = 0;//清空

    			ku ++;//换一个连通块的名称

    		}

    	}

    }

    for(int i = 1;i <= m;i++)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		cout<<c[b[x][y]]<<endl;

	}

	return 0;

}