글 읽기 - 16946 질문드립니다.

gwang92 10달 전 0

아래 테스트케이스는 잘 돌아갑니다.
어느 부분이 틀렸을까요 혹은 반례가 있다면 답글 부탁드립니다.

* 추가

배열 크기 문제로 계속 fail이었네요

넘버링의 가장 큰 수는 최대 (N/2)*N 이기 때문에

1000/2*1000 인 500001의 배열크기로 변경했더니 통과했습니다.

INPUT

3 4

0010

0000

OUTPUT

0020

0000

INPUT

7 7
1111111
1000001
1011101
1010101
1011101
1000001
1111111

OUTPUT
1777771
7000007
7078707
7080807
7078707
7000007
1777771

INPUT

6 6
101010
000000
101010
000000
101010
000000

OUTPUT
808080
000000
808080
000000
808080
000000

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#define MAX 1001
using namespace std;

int dy[]={0,1,0,-1},dx[]={1,0,-1,0};
queue<pair<int,int>> q,backup;
vector<pair<int,int>> v;
int N,M,map[MAX][MAX],visit[MAX][MAX],arr[MAX],check[MAX],cnt;

void game(){
	// 0 인곳 넘버링 
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			if(visit[i][j])continue;
			visit[i][j]=1; cnt++; arr[cnt]++;
			q.push({i,j}); backup.push({i,j});
			while(!q.empty()){
				auto now=q.front();q.pop();
				int y=now.first,x=now.second;
				for(int k=0;k<4;k++){
					int ny=y+dy[k],nx=x+dx[k];
					if(ny<0 || nx<0 || ny>N-1 || nx>M-1 || visit[ny][nx]) continue;
					visit[ny][nx]=1; q.push({ny,nx}); arr[cnt]++;
					backup.push({ny,nx});
				}
			}
			while(!backup.empty()){
				auto now=backup.front();backup.pop();
				visit[now.first][now.second]=cnt;
			}
		}
	}
	
	// map에 이동경로 표시하기 
	for(int i=0;i<v.size();i++){
		int y=v[i].first,x=v[i].second,sum=0;
		for(int j=0;j<4;j++){
			int ny=y+dy[j],nx=x+dx[j];
			if(ny<0 || nx<0 || ny>N-1 || nx>M-1 || check[visit[ny][nx]] || map[ny][nx]) continue;
			check[visit[ny][nx]]=1;
			sum+=arr[visit[ny][nx]];
		}
		map[y][x]=sum+1;
		memset(check,0,sizeof(check));
	}
}	

int main(){
	scanf("%d %d",&N,&M);
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			scanf("%1d",&map[i][j]);
			visit[i][j]=map[i][j];
			if(map[i][j]){
				v.push_back({i,j});	
			} 
		}
	}
	game();
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			printf("%d",map[i][j]%10);
		}
		printf("\n");
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

16946 질문드립니다.

gwang92 10달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말