F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Paint on a Wall

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1610    Accepted Submission(s): 665


Problem Description
Annie wants to paint her wall to an expected pattern. The wall can be represented as a 2*n grid and each grid will be painted only one color. Annie has a brush which could paint a rectangular area of the wall at a single step. The paint could be overlap and the newly painted color will replace the older one.
  For a given pattern of the wall, your task is to help Annie find out the minimum possible number of painting steps. You can assume that the wall remains unpainted until Annie paint some colors on it.
 

Input
There are multiple test cases in the input. The first line contains the number of test cases.
  For each test case, the first line contains the only integer n indicating the length of the wall. (1 <= n <= 8)
  Two lines follow, denoting the expected pattern of the wall. The color is represented by a single capital letter.
  See the sample input for further details.
 

Output
For each test case, output only one integer denoting the minimum number of steps.
 

Sample Input
3 3 ABA CBC 3 BAA CCB 3 BBB BAB
 

Sample Output
Case #1: 3 Case #2: 3 Case #3: 2
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 16:18:33, Gzip enabled