Submission #22701

#	Time	Username	Problem	Language	Result	Execution time	Memory
22701		카시코이 (#40)	Young Zebra (KRIII5_YZ)	C++11	7 / 7	33 ms	4692 KiB

YZ

#include <cstdio>
#include <queue>
using namespace std;

struct st{
  int x, y, fx, fy;
};

char s[410][410];
int cur[410][410];
int firstX[410][410];
int firstY[410][410];

int arr[160010];

queue<st> q;
int dir[4][2] = {-1, 0, 0, -1, 0, 1, 1, 0};

int main(){
  int N, M; scanf("%d%d", &N, &M);
  for(int i = 0; i < N; i++) scanf("%s", s[i]);

  int c = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      if(cur[i][j] != 0) continue;

      // puts("new group");

      cur[i][j] = ++c; int cnt = 1;
      while(!q.empty()) q.pop();
      q.push({i, j, 0, 0});

      while(!q.empty()){
        st n = q.front(); q.pop();
        // printf("%d %d %d %d\n", n.x, n.y, n.fx, n.fy);

        for(int d = 0; d < 4; d++){
          int x = n.x + dir[d][0], y = n.y + dir[d][1];
          int fx = n.fx, fy = n.fy;

          if(x < 0){ x += N; fx--; }
          if(y < 0){ y += M; fy--; }
          if(x >= N){ x -= N; fx++; }
          if(y >= M){ y -= M; fy++; }

          // printf("cand : %d %d %d %d\n", x, y, fx, fy);
          if(s[x][y] != s[n.x][n.y]) continue;

          if(cur[x][y] == 0){
            q.push({x, y, fx, fy}); cur[x][y] = c; firstX[x][y] = fx; firstY[x][y] = fy;
            cnt++;
          }
        }
      }
      arr[c] = cnt;
    }
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      for(int d = 0; d < 4; d++){
        int x = i + dir[d][0], y = j + dir[d][1];
        int fx = 0, fy = 0;

        if(x < 0){ x += N; fx--; }
        if(y < 0){ y += M; fy--; }
        if(x >= N){ x -= N; fx++; }
        if(y >= M){ y -= M; fy++; }

        if(cur[i][j] == cur[x][y]){
          if(firstX[i][j] + fx != firstX[x][y] || firstY[i][j] + fy != firstY[x][y]){
            arr[cur[i][j]] = -1;
          }
        }
      }
    }
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++) printf("%d ", arr[cur[i][j]]);
    printf("\n");
  }
  return 0;
}

Compilation message (stderr)

YZ.cpp: In function 'int main()':
YZ.cpp:20:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int N, M; scanf("%d%d", &N, &M);
                                  ^
YZ.cpp:21:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 0; i < N; i++) scanf("%s", s[i]);
                                               ^

• Subtask 1: 7 / 7