东莞网站建设周期,三门县住房和城乡建设规划局网站,小狐狸动画制作软件app下载,如何做一个企业网站正题 题目大意
在一个n*n的棋盘上进行m此操作。在一个格子上放一个黑或白的棋子。多个相连的同色棋子形成一个连通块#xff0c;求每次操作后求连通块数。 解题思路
并查集表示连通#xff0c;然后每次扩展#xff0c;如果有同色的就连通#xff0c;注意判断已经是同一个…正题 题目大意
在一个n*n的棋盘上进行m此操作。在一个格子上放一个黑或白的棋子。多个相连的同色棋子形成一个连通块求每次操作后求连通块数。 解题思路
并查集表示连通然后每次扩展如果有同色的就连通注意判断已经是同一个连通块的情况。 代码
#includecstdio
using namespace std;
int n,m,s,c,x,y,color[601][601],father[250001];
int dx[4]{1,-1,0,0},dy[4]{0,0,1,-1};
int find(int x)
{return xfather[x]?x:find(father[x]);}
//找祖先
int number(int x,int y)
{return (x-1)*ny;}//求号
bool unionn(int x,int y)
{int fafind(x),fbfind(y);if (fafb) return 0;if (fafb) father[fb]fa;else father[fa]fb;return 1;
}//相连并放回是否已经在同一连通块
int main()
{//freopen(blocks.in,r,stdin);f//reopen(blocks.out,w,stdout);scanf(%d%d,n,m);for (int i1;in*n;i) father[i]i;s0;for (int i1;im;i){scanf(%d %d %d,c,x,y);c;color[x][y]c;//标记s;//连通块增加for (int k0;k4;k){int zxxdx[k],zyydy[k];if (zx0zxnzy0zyncolor[x][y]color[zx][zy]){if(unionn(number(x,y),number(zx,zy)))s--;//合并注意判断是否在同一连通块}}printf(%d\n,s);}
} 对拍
随机数据与暴力
#includecstdio
#includectime
#includecstdlib
#includestring
#includeiostream
#includemap
#define random(x) rand()%x1
using namespace std;
int n,m,s,color[501][501],c,x,y,e[501][501];
bool f[501][501];
void bfs(int x,int y,int c,int w)
{if (xn || yn || x1 || y1 || color[x][y]c || !color[x][y])return;if (f[x][y] || e[x][y]!w) return;f[x][y]true;bfs(x1,y,c,w);bfs(x-1,y,c,w);bfs(x,y1,c,w);bfs(x,y-1,c,w);
}
int main()
{freopen(blocks.in,w,stdout);srand((unsigned)time(0));nrandom(500);mrandom(n*n);printf(%d %d\n,n,m);for (int i1;im;i){crandom(2)-1;xrandom(n);yrandom(n);while (color[x][y]){xrandom(n);yrandom(n);}printf(%d %d %d\n,c,x,y);color[x][y]i;e[x][y]c;}fclose(stdout);freopen(blocks.ans,w,stdout);for (int k1;km;k){memset(f,0,sizeof(f));s0;for (int i1;in;i)for (int j1;jn;j)if (!f[i][j] color[i][j]k color[i][j]){bfs(i,j,k,e[i][j]);s;}printf(%d\n,s);}fclose(stdout);
}
对拍
#includecstdio
#includectime
#includecstdlib
#includecstring
using namespace std;
int main()
{for (int t1;t100000;t){system(blocksdata.exe);double stclock();system(blocks.exe);double edclock();if (system(fc blocks.out blocks.ans)){printf(WA);return 0;}elseprintf(AC point:%d time:%.0lfms\n,t,ed-st);}
}
