hiho一下 第232周

题目1：拆字游戏

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述
小Kui喜欢把别人的名字拆开来，比如“螺”就可以拆成“虫田糸”，小Kui的语文学的不是很好，于是她决定使用编程的方式来解决这个问题。给出一个01矩阵，1占据的部分即为需要拆的字，如果两个1分享一条边，那么它们连通。连通具有传递性，即如果a、b连通，b、c连通，则a、c连通。连通的一系列1被看做可以拆出的一块，现在小Kui需要输出这些拆出的块（用一个01矩阵表示，并且要求矩阵的大小尽可能的小）。为了确保输出的顺序尽可能的和书写的顺序一致，小Kui从每个块中选出最左上角的点（最左侧的点中，最靠上的）作为代表点，然后按照代表点从左到右（若相同则按从上到下）的顺序输出所有拆出的块。

输入
输入的第一行为两个正整数N、M，表示01矩阵的大小。

接下来N行，每行M个01字符，描述一个需要拆的字。

对于40%的数据，满足1<=N,M<=10。

对于100%的数据，满足1<=N,M<=500。

输出
按照代表点从左到右（若相同则按从上到下）的顺序输出所有拆出的块。

对于每个块，先输出其大小，然后用对应的01矩阵表示这个块。

样例

样例输入	样例输出
11 17 00000000000000000 00001111111100000 00000000000000000 00111111111111100 00000000100000000 00000010101110000 00000110100011000 00011100100001000 00000010100000000 00000001100000000 00000000000000000	7 13 1111111111111 0000001000000 0000001000000 0000001000000 0000001000000 0000001000000 0000011000000 3 4 0001 0011 1110 1 8 11111111 1 1 1 3 4 1110 0011 0001

额外的样例

样例输入	样例输出
14 22 0000000000001111111100 0000000000001101101100 0000110000001111111100 0000110000001101101100 0111111110001111111100 0110110110000000000000 0110110110000011000000 0111111110001111111000 0000110000000001100000 0000110110001111111100 0111111111000111111000 0000000010001101101100 0000000000000001100000 0000000000000011100000	10 9 000110000 000110000 111111110 110110110 110110110 111111110 000110000 000110110 111111111 000000010 5 8 11111111 11011011 11111111 11011011 11111111 8 8 00110000 11111110 00011000 11111111 01111110 11011011 00011000 00111000

思路

赛时，一看到题目就觉得要逐点并查集合并一下，然后再将每个合并块输出，但实现起来还是颇为麻烦的。后来想想，自己还是想复杂了，直接逐点深搜或者广搜都行，注意要边搜边将已经搜过的块打好标记就是。C++选手刚转型Java选手，上来就拿Java试手，交了一发Java版dfs，结果TLE。没道理啊，考虑到bfs可能会快一点，于是转一手Java版bfs，还是TLE。看了好几遍，思路代码都没问题的呀，百思不得其解，莫非是Java语言本身运行的慢而题目却没有给Java增加额外的耗时，于是将我打回C++原形，写了两发C++的dfs和bfs，结果全都是TLE只过百分之40的数据。后来后来。。。才发现，C++里是我在双重循环里memset整个505505的数组而造成极大的开销(Java里则是在双重循环里面new出505505的数组)，改成预先定义好最大数组然后每次手动for循环重置数组就AC了。。。。

我的方法是把每次搜到的结果放到res数组里，并且在搜索时，每搜到一个点都需要判断当前点与sx,sy,px,py的大小，从而获得搜索路径的左上角坐标和左下角坐标进而得到搜到块的大小。

原来memset要慎用！！！直接对最大数组memset(尤其是如果在循环里面需要多次重置!)，还不如手动对已知数组范围进行重置清零！！！
从此再也不敢用memset偷懒了(逃

我的代码

Java    dfs/bfs

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
  public static InputReader in = new InputReader(new BufferedInputStream(System.in));
  public static PrintWriter out = new PrintWriter(System.out);
  public static char[][] Map;
  public static int[][] res = new int[505][505];
  public static int[][] vis = new int[505][505];
  public static int sx, sy, px, py;
  public static int dx[] = {1, 0, -1, 0};
  public static int dy[] = {0, 1, 0, -1};
  public static int n, m;

  public static void main(String[] args) {
    String s;
    Map = new char[505][505];
    n = in.nextInt();
    m = in.nextInt();
    for (int i = 1; i <= n; i++) {
      s = in.nextLine();
      for (int j = 1; j <= m; j++) {
        Map[i][j] = s.charAt(j - 1);
      }
    }
    for (int j = 1; j <= m; j++) {
      for (int i = 1; i <= n; i++) {
        if (Map[i][j] == '1') {
          px = i;
          py = j;
          sx = i;
          sy = j;
          vis[i][j] = '2';
          res[i][j] = 1;
          dfs(i, j);
          out.println((px - sx + 1) + " " + (py - sy + 1));
          out.flush();
          for (int k = sx; k <= px; k++) {
            for (int p = sy; p <= py; p++) {
              out.print(res[k][p]);
              out.flush();
              if (res[k][p] != 0)
                res[k][p] = 0;
              if (vis[k][p] != 0)
                vis[k][p] = 0;
            }
            out.println();
            out.flush();
          }
        }
      }
    }
    out.close();
  }

  static void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if (nx > 0 && nx <= n && ny > 0 && ny <= m && vis[nx][ny] == 0 && Map[nx][ny] == '1') {
        vis[nx][ny] = 1;
        res[nx][ny] = 1;
        if (nx > px) {
          px = nx;
        }
        if (ny > py) {
          py = ny;
        }
        if (nx < sx) {
          sx = nx;
        }
        if (ny < sy) {
          sy = ny;
        }
        Map[nx][ny] = '2';
        dfs(nx, ny);
        vis[nx][ny] = 0;
      }
    }
  }

  static class Point {
    int x, y;
  }

  static void bfs(int x, int y) {
    Queue<Point> queue = new LinkedList<>();
    Point now = new Point();
    now.x = x;
    now.y = y;
    queue.add(now);
    vis[x][y] = 1;
    while (!queue.isEmpty()) {
      now = queue.poll();
      out.flush();
      for (int i = 0; i < 4; i++) {
        Point next = new Point();
        next.x = now.x + dx[i];
        next.y = now.y + dy[i];
        if (next.x > 0 && next.x <= n && next.y > 0 && next.y <= m && vis[next.x][next.y] == 0
            && Map[next.x][next.y] == '1') {
          vis[next.x][next.y] = 1;
          res[next.x][next.y] = 1;
          if (next.x > px) {
            px = next.x;
          }
          if (next.y > py) {
            py = next.y;
          }
          if (next.x < sx) {
            sx = next.x;
          }
          if (next.y < sy) {
            sy = next.y;
          }
          Map[next.x][next.y] = '2';
          queue.add(next);
        }
      }
    }
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String nextLine() {
      String str = null;
      try {
        str = reader.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }
}

C++    dfs

#include<bits/stdc++.h>
using namespace std;
char Map[505][505];
int res[505][505];
int vis[505][505];
int sx, sy, px, py;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m;
void dfs(int x, int y) {
  for(int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(nx > 0 && nx <= n && ny > 0 && ny <= m && vis[nx][ny] == 0 && Map[nx][ny] == '1') {
      vis[nx][ny] = 1;
      res[nx][ny] = 1;
      Map[nx][ny] = '2';
      if(nx > px) {
        px = nx;
      }
      if(ny > py) {
        py = ny;
      }
      if(nx < sx) {
        sx = nx;
      }
      if(ny < sy) {
        sy = ny;
      }
      dfs(nx, ny);
      vis[nx][ny] = 0;
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++) {
    getchar();
    for(int j = 1; j <= m; j++) {
      scanf("%c", &Map[i][j]);
    }
  }
  for(int j = 1; j <= m; j++) {
    for(int i = 1; i <= n; i++) {
      if(Map[i][j] == '1') {
        px = i;
        py = j;
        sx = i;
        sy = j;
        Map[i][j] = '2';
        res[i][j] = 1;
        dfs(i, j);
        printf("%d %d\n", (px - sx + 1), (py - sy + 1));
        for(int k = sx; k <= px; k++) {
          for(int p = sy; p <= py; p++) {
            printf("%d", res[k][p]);
            if(res[k][p]) res[k][p] = 0;
            if(vis[k][p]) vis[k][p] = 0;
          }
          printf("\n");
        }
      }
    }
  }
  return 0;
}

C++    bfs

#include<bits/stdc++.h>
using namespace std;
char Map[505][505];
int res[505][505];
int vis[505][505];
int sx, sy, px, py;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m;
struct Point {
  int x, y;
};
void bfs(int x, int y) {
  queue<Point> queue;
  Point now;
  now.x = x;
  now.y = y;
  queue.push(now);
  vis[x][y] = 1;
  while(!queue.empty()) {
    now = queue.front();
    queue.pop();
    for(int i = 0; i < 4; i++) {
      Point next;
      next.x = now.x + dx[i];
      next.y = now.y + dy[i];
      if(next.x > 0 && next.x <= n && next.y > 0 && next.y <= m && vis[next.x][next.y] == 0 && Map[next.x][next.y] == '1') {
        vis[next.x][next.y] = 1;
        res[next.x][next.y] = 1;
        if(next.x > px) px = next.x;
        if(next.y > py) py = next.y;
        if(next.x < sx) sx = next.x;
        if(next.y < sy) sy = next.y;
        Map[next.x][next.y] = '2';
        queue.push(next);
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++) {
    getchar();
    for(int j = 1; j <= m; j++) {
      scanf("%c", &Map[i][j]);
    }
  }
  for(int j = 1; j <= m; j++) {
    for(int i = 1; i <= n; i++) {
      if(Map[i][j] == '1') {
        px = i;
        py = j;
        sx = i;
        sy = j;
        vis[i][j] = '2';
        res[i][j] = 1;
        bfs(i, j);
        printf("%d %d\n", (px - sx + 1), (py - sy + 1));
        for(int k = sx; k <= px; k++) {
          for(int p = sy; p <= py; p++) {
            printf("%d", res[k][p]);
            if(res[k][p]) res[k][p] = 0;
            if(vis[k][p]) vis[k][p] = 0;
          }
          printf("\n");
        }
      }
    }
  }
  return 0;
}

最后更新： 2018年12月17日 18:45

原始链接： http://yoursite.com/2018/12/17/hihoCoder Week232 question01/

dailingx

赏

× 请我吃糖~