MatrixTransforming
SRM 311 · 2006-07-12 · by gevak
SRM 311 · 2006-07-12 · by gevak · Greedy
Problem Statement
Problem Statement
Given two matrices a and b, both composed of zeroes and ones, return the minimal number of operations necessary to transform matrix a into matrix b. An operation consists of flipping (one becomes zero and zero becomes one) all elements of some contiguous 3 x 3 submatrix. If a cannot be transformed into b, return -1.
Constraints
- a will contain between 1 and 50 elements, inclusive.
- a and b will contain the same number of elements.
- Each element of a will contain between 1 and 50 characters, inclusive.
- Each element of b will contain between 1 and 50 characters, inclusive.
- All elements of a and b will contain the same number of characters.
- Each element of a and b will be contain only zeroes ('0') and ones ('1').
Examples
0)
{"111","111","111"}
{"000","000","000"}
Returns: 1
Flip the entire 3 x 3 matrix.
1)
{"1"}
{"0"}
Returns: -1
No flip can be made here.
2)
{"0010100111000100100101100000011100000011001011","0011110111001100001101110011101101001110111101","1101100110110111110110110010101101011000101101","1000000000001100010110111110100111000010101001","0000001010001011010110010001101001011111100101","0001100001010110111000100100100111101010001110","0100101100011111101010110001110011010100000100","1011010111011011010000101101011001110011111101","1111101001111011011100010101100000010001110010","0100000011111011111111111000110011100110001001","0010101000010010011110001011100000110111101101","0010111100110100011000011011100011011100000010","0100101110011110011001100010000010110001011111","0000011110100110101001111001011111110110100111","1111001111000101000111101111111010111111011100","1001110101111001111101011000011000110100101110","1000110111100110100101111101011111010101011101","0000111011000000001110000101010110110001110101","0110111101110010101001000011010101111001010101","1111101110101100010000100001110000100000100011","0111101100011010010010000101110011001100011011","0011101010010000001100110110001010101001000011","0010000111010011101101000000011010011001110000","0110011100100100010001000000111100011001100001","1100111010100111100100110011110101100101110011","1010101001011000001110000111001100111000101101","0100010011101111100110000011101111011111111110","1001011000010001000100101110101001001100101001","0100100000101001010010101110000011110101001010","1000111100000000111011001000100011111011101001","0100010110010000010001000100011010111111010011","1101001101001000011011110010110001000110011000","1001001000110110010100100110110010000011001001","1110011110010010101100010100111100100110110111","1101000100000110101001101001000111010011000000","0111011001100010000001100000111011101110101000"}
{"1011100001110110001101001000110100001110101011","1110000011100010011110111011111001100001111011","0011100011111110000001111001000101100110000101","1110110111100111011100101110111101000100011111","0010001111000010101011000001111110011010001111","0010110010000010000011101001110100111110000011","0101101000111011011011010111001010101000110000","0011111101101100111110000100010000011010010011","0011010111001010100110010100011000000011001101","1000011010110000011100111010111010111101110001","0100001100101101101101011011001001100101101111","1011010011111010111110010010010001000011001100","1001011011111010000000101001110011010111101011","0000111110101111010011001001100010101011001001","0001101110111000011110001101111101010100010111","1101101010010010101100111100101011111011100001","0011000000100000010101010111000010110110011111","1111010110101010011111110010111010000001110001","0101001100110101100100110101001110100111110011","0010000000010111000001101001000111110010010010","1001000110010100011001010001111000111010101011","1101001011001001101111010100000000111000100001","0010011111010110100011100000000010101101100110","0000010000011010000100011110001111110010000001","1011011101000110010101001110100010101011100000","1100011011100111001010001001101111110010011110","0100110001010111011001001101101011110010111011","1111010111101111110010010010011010110111110001","0100011111010010000100100101111001001110011100","1000101110100011000110010110100101010010100010","0010000111100010100010100110101010110101001000","0100001110011001111101011110110110001011001101","0011111010000011000101010011100100001011111110","0100101001011100011100111110011110001110110000","1110001100001001101001111101010010111011001001","0111101110001101000110111010101010011110101000"}
Returns: 497
3)
{"100011110000000","101110111111101","110101110100100","100000110111100","011100100000000","001100001011101","101010100111011","010110010110010","111101000101010","000000110101000","100101010000101","111011100001111","101101100111000","001010001110010","100010001011011","110011001100000","011100011101011","010000010100101","001110110000100","010011111010110","011011100100110","001000101011001","101011101100011","011101001101000","000100000011001","001111000110100","111011010111111","011000110110010","010100110010001","001000101000000","001110110110100","000010010111111","100100011100110","101010001011010","101111011001001","101100010010010","110011110111011","100010011101111","110111110111010","010110101101001","100000010000010","011111011000100","111001010010100","011101011000011","110010011111101","110110010011011","011011010000111","110000110110000"}
{"000100101001110","111111110011011","100111000001000","011100100100110","000101110001110","101100001010111","001011101111000","101101111000010","110001110110101","111001101101010","111110010000010","111000100111101","010000010100000","001110110100011","001111100111101","010000100001111","011011010011011","101100000111111","110011011101001","000100010111100","011010011010001","100101110010011","011110010111011","000000001101001","011111101110001","011110100101000","011110001000010","101000110111010","111001100000001","100001101110101","010000110100011","001111010001101","100100101010110","100110001000011","100101000000000","001100101010110","100000110000010","101110100111000","001001111010000","001111010101011","001001011001001","010101111110010","110100010001011","110101001101001","101010000010111","010011000000100","110010111011010","010110100101011"}
Returns: 258
4)
{"10101001001011110000110101010101001001010","11101110100001101100000011100010110001101","10111111100011100101101000100100011110000","10000001001100110100001100110111100110010","01011101011000101111011011011111100101001","10010100011100111101011110000010001011010","10111000011010010101011111100110111100001","11101110111101000001100001100010010101100","10110000110000101000101010001011011010111","01000111100100000001000000001000111010011","10010011011101110010000111010100000001000","01010110010110000100011100111101110110101","00100100101000101011010101111111101111111","00111111011001101001101010010101110111100","11110111110001101101111000011000011000110","10010101110100011010001101000101000110000","00110101011101000011110001010101011011100","01100000000111100010000100001001010111110","11010110110010100001111010010101011000100","00111101010010110110011000100010010111111","11011000001001011010110011000011010100101","00110001010010010000000011110000101111100","10000110001110001111001010110001101110101","00001111101000111111100001101001110111011","01001110101100101101010100100011011101111","01100001000011111111011101110100011110111","01011110100100101111110010101100000110100","11000010110001000010110101000111010100100","10010111110001001100100100011100110100111","11011110110110000011110001011100001010011","01010101100110010110110100100101011001110","11111111110101110101110110111001010010100","11000101101011001101011011011110101011001","00011010010011111010001100000111110101101","00101011010011000001101111100010010001011","11011110011110110111110010010110100110000","01001010111011101011101011011010101101110","11110011101100100010100010011011110001001","00000000110011010000110001010010011110100","11111110101011010110010101011100110000100","10011101010001101001110110101010110100001","10000111110011100110111110100011010100110","00111000010111011101010100000111011100101"}
{"10101001001100110000101001101010110001010","11101111010110110111011000011101001001101","10111110010100111110110011000111100110000","10000000111111001111001011101000000001101","01011101011011001111000111000011100010110","11100100011111000001000010000010000010101","11110011111010110000110100111001010011111","11101101011101100100010110111110011011100","11000011001100010001000101110111011010111","00000001111000111000100001101001010111101","10011101000001001011111010110101101101111","01011000011000111110011000010001100100010","00100100100110101000101011110010001101000","00111111001011101010010100011000010101100","11110111101101101101100000111000000100110","10010101101000011010011000000101000110000","00110101100101000011111000010101011011100","01100000111111100010010110101110111001110","11010110010001100110100001110010110110100","00111010001001110010100011000101111010100","11011100110010011110011101000100010111110","00111011001010010011110001110111010100111","10011001001010001111100000110110010110101","00010011001100111111000010101001001101001","01011100110000110001100010100000111111010","01100001000011100011010011110100011100010","01011110111000110011110010101100111110011","11000011000111110101111011000101111100100","10010001000001001011101010011111101011111","10101000011011110100110000101111110010111","00100001000001010110110101010111011100110","10001101100100000010111001001000110000100","11000111111011001010010010011111010110010","00011011111111111101001001010110000100100","00010011001111000001100011110001110111101","00001000000010110100011010100101000111001","10011100111011100101101111111001001101001","00011101101100101100111010100000001110001","00000000110011011101001010001001100110100","11111110101011010110000000000111110000100","10011101010001101001111000101010001011001","10000111110011100110110000100011101011110","00111000010111011101010100000111011011101"}
Returns: 142
32)
{
"0000",
"0010",
"0000"
}
{
"1001",
"1011",
"1001"
}
Returns: 2
Flip each of the two 3 x 3 submatrices once.
Submissions are judged against all 65 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MatrixTransforming with a public method int minPushes(vector<string> a, vector<string> b) · 65 test cases · 2 s / 256 MB per case