公司网站怎么自己制作,秦皇岛 网站,wordpress首页打开很慢,全国全屋定制品牌十大排名洛谷题目链接
Atcoder题目链接
分析
发现将每个红色连通块涂成绿色连通块后#xff0c;绿色连通块个数会加一#xff0c;但是如果这个连通块之前已经跟绿色连通块相邻#xff0c;则连通块数量减一。
代码
#include bits/stdc.h
#define int long longusing nam…洛谷题目链接
Atcoder题目链接
分析
发现将每个红色连通块涂成绿色连通块后绿色连通块个数会加一但是如果这个连通块之前已经跟绿色连通块相邻则连通块数量减一。
代码
#include bits/stdc.h
#define int long longusing namespace std;const int N 1005, mod 998244353;
int n, m, cnt, ans, tot, vis[N][N];
int dx[] {0, 0, -1, 1}, dy[] {-1, 1, 0, 0};
char c[N][N];void dfs(int x, int y, int d){if(c[x][y] ! # || vis[x][y]){return ;}vis[x][y] d;for(int i 0; i 4; i ){int nx x dx[i], ny y dy[i];dfs(nx, ny, d);}
}
int qpow(int n, int m, int p){ int res 1;while(m){if(m 1){res res % p * n % p;}n n % p * n % p;m 1;}return res;
}signed main(){cin n m;for(int i 0; i n 1; i ){for(int j 0; j m 1; j ){c[i][j] 6;}}for(int i 1; i n; i ){for(int j 1; j m; j ){cin c[i][j];}}for(int i 1; i n; i ){for(int j 1; j m; j ){if(c[i][j] # !vis[i][j]){cnt ;dfs(i, j, cnt);}}}for(int i 1; i n; i ){for(int j 1; j m; j ){if(c[i][j] .){tot ;map int, bool mp;for(int k 0; k 4; k ){int nx i dx[k], ny j dy[k];if(c[nx][ny] #){mp[vis[nx][ny]] true;}}ans cnt - mp.size() 1;ans % mod;}}}cout ans * qpow(tot, mod - 2, mod) % mod;return 0;
}
