51nod 1448 2 염색 문제 (아이디어 문제, 좋 은 문제)

제목 링크
1448 이염 색 문제
제목: TopCoder
기준 시간 제한: 1 초 공간 제한: 131072 KB 값: 40 난이도: 4 단계 알고리즘 문제
수장 하 다
관심 을 가지다
N * N 의 격자 입 니 다. 처음에는 흰색 입 니 다.현재 K * K 의 인장 이 있 습 니 다. 매번 조작 할 때마다 도장 으로 격자 에 있 는 K * K 의 자 사각형 을 검은색 이나 흰색 으로 염색 할 수 있 습 니 다.만약 한 칸 이 여러 번 염색 된다 면, 다음 염색 은 이전 염색 을 덮어 버 릴 것 이다.현재 N * N 의 흑백 2 색 으로 구 성 된 패턴 보드 (board [i] [j] 는 i 행 j 열 칸 의 색상 입 니 다. 알파벳 'W' 가 아니 라 검은색 은 알파벳 'B' 로 표시 합 니 다) 를 드 립 니 다. 몇 번 의 조작 을 통 해 격자 를 초기 상태 에서 패턴 보드 의 모양 으로 염색 할 수 있 는 지 물 어보 세 요."Possible" 을 출력 할 수 있다 면, 그렇지 않 으 면 "Impossible" 을 출력 합 니 다.
Input

      ，       T，        ，1<=T<=5
              ：
          N K,  1<=K<=N<=20。
  N ，  N   ，  board，    ‘W’ ‘B’  。

Output

        ，       board   。

입력 예제

3
4 3
BBBW
BWWW
BWWW
WWWW
2 2
BW
WB
6 2
BWBWBB
WBWBBB
BWBWBB
WBWBBB
BBBBBB
BBBBBB

출력 예제

Possible
Impossible
Possible

공식 문제 풀이:
역방향 사 고 를 시도 할 수 있 습 니 다. 마지막 부분 은 검은색 이 든 흰색 이 든 모두 k * k 의 연결 부분 입 니 다.마지막 i 블록 은 그 일부분 이 마지막 i - 1 블록 에 가 려 지고 나머지 부분 은 반드시 같은 색 이 며 k * k 의 사각형 에 분포 한다.따라서 작은 정사각형 이 덮 일 때 까지 욕심 구 조 를 역방향 으로 구성 할 수 있다.
사실 이 문 제 는 예전 에 했 던 포스터 를 붙 이 는 문제 와 같 습 니 다. 먼저 모두 같은 색 의 k * k 블록 을 확인 한 다음 에 이 블록 안의 칸 을 방문 한 것 으로 표시 합 니 다. 뒤의 k * k 블록 에 대해 서 는 이미 방문 한 점 을 제외 하고 다른 것 이 같은 색 인지 아 닌 지 판단 하고 이런 블록 을 찾 지 못 할 때 까지 마지막 으로 한 번 더 스 캔 합 니 다.접근 되 지 않 은 블랙 이 존재 한다 면 해결 방안 이 존재 하지 않 는 다 는 뜻 이다.

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define rep(i,a,n) for (int i=a;i=a;i--)
#define pb push_back
#define fi first
#define se second
typedef vector VI;
typedef long long ll;
typedef pair PII;
const ll mod=1000000007;
const int maxn=20+10;
char s[maxn][maxn];
bool vis[maxn][maxn];
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        memset(vis,false,sizeof(vis));
        int n,k;
        scanf("%d%d",&n,&k);
        bool flag=true;
        for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
        while(flag)
        {
            flag=false;
            for(int i=1;i<=n-k+1;i++)
            {
                for(int j=1;j<=n-k+1;j++)
                {
                    int sum1=0,sum2=0;
                    bool f=false;
                    for(int ii=i;ii

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

51nod 1448 2 염색 문제 (아이디어 문제, 좋 은 문제)

제목 링크 1448 이염 색 문제 제목: TopCoder 기준 시간 제한: 1 초 공간 제한: 131072 KB 값: 40 난이도: 4 단계 알고리즘 문제 몇 번 의 조작 을 통 해 격자 를 초기 상태 에서 패턴...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

51nod 1448 2 염색 문제 (아이디어 문제, 좋 은 문제)

좋은 웹페이지 즐겨찾기