锐客网

  1. 首页 > it技术 > >

CodeForces 377A

DFS

原来是想在填X的时候一边判断 ’.‘ 区域的连通性，发现很麻烦，说不定还超时。
另一种思路是，求出’.‘的数量是cou，需要填k个’X‘，则只需要找到一个有cou-k 个’.‘的连通域就可以了，剩下的k个’.‘全换成’X ‘
【CodeForces 377A】

#include #include #include int n, m, k; char mapp[510][510]; int vis[510][510]; int sizev = sizeof(vis); int cou, cc; int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} }; ///四个方向bool check(int x, int y) { if (x >= n || x < 0 || y >= m || y < 0 || vis[x][y]) return false; ///越界和标记判断 return true; }void dfs(int x, int y) { if (cc == k) return ; ///达到要求int i; for (i = 0; i < 4; i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; if (!check(nx, ny)) continue; vis[nx][ny] = 1; mapp[nx][ny] = 'z'; ///标记图中的‘.’ cc++; dfs(nx, ny); if (cc == k) return ; ///达到连同域中‘.’的数量要求，不用再找了 }}int main() { int i, j; int s_x, s_y; while (~scanf("%d%d%d", &n, &m, &k)) { memset(vis, 0, sizev); cou = 0; cc = 0; for (i = 0; i < n; i++) {scanf("%s", mapp[i]); for (j = 0; j < m; j++) { if (mapp[i][j] == '.') { cou++; s_x = i; ///记录最后一个‘.’的位置，以此为基准求连通域 s_y = j; }if (mapp[i][j] == '#') vis[i][j] = 1; ///墙不能走} }k = cou - k; ///关键，转换的一步cc++; mapp[s_x][s_y] = 'z'; vis[s_x][s_y] = 1; dfs(s_x, s_y); for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { if (mapp[i][j] == 'z') putchar('.'); else if (mapp[i][j] == '.') putchar('X'); else printf("%c", mapp[i][j]); } puts(""); } } return 0; }



    推荐阅读


    上一篇：LeetCode|LeetCode总结，位运算总结

    下一篇：Java|Java 关于集合(1)