题目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了。。。。

四发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());
    }
  }
}