Untitled
unknown
c_cpp
2 months ago
9.0 kB
15
Indexable
struct TestCase {
int width;
int height;
int nbBlocks; // Number of blocks in the grid
vector<string> grid; // The grid itself
int expectedOutput; // The expected output of the solve function
};
char BLOCK = '-';
bool checkRight(int i, int j, vector<string> &grid, char num) {
while (j < grid[i].size()) {
if (grid[i][j] == BLOCK) {
return true;
}
if (grid[i][j] == num || grid[i][j] == '.') {
// grid[i][j] = BLOCK;
j++;
} else if (grid[i][j] == 'X' or grid[i][j] != '.') {
return false;
}
// j++;
}
return true; // reached end
}
bool isObstructued(int i, int j, char num, vector<string> &grid) {
if (i < 0 or i >= grid.size() or j < 0 or j >= grid[i].size() || grid[i][j] != num) {
return true; // Out of the grid scope
}
int a = i - 1;
int b = j;
int c = i + 1;
int d = j;
grid[i][j] = BLOCK;
while (a >= 0 && grid[a][b] == num) {
bool ans = checkRight(a, b, grid, num);
if (!ans) return false;
a--;
}
// cout << "Upper Passed for " << num << " at " << i << ", " << j << endl;
while (c < grid.size() && grid[c][d] == num) {
bool ans = checkRight(c, d, grid, num);
if (!ans) return false;
c++;
}
// cout << "Lower Passed for " << num << " at " << i << ", " << j << endl;
return isObstructued(i + 1, j, num, grid) and isObstructued(i - 1, j, num, grid) and isObstructued(i, j + 1, num, grid) and isObstructued(i, j - 1, num, grid);
}
void exitBlock(int i, int j, char num, vector<string> &grid) {
if (i < 0 or i >= grid.size() or j < 0 or j >= grid[i].size() or grid[i][j] != num) {
return;
}
grid[i][j] = '.';
exitBlock(i + 1, j, num, grid);
exitBlock(i - 1, j, num, grid);
exitBlock(i, j + 1, num, grid);
exitBlock(i, j - 1, num, grid);
}
int solve(int height, int width, int n, vector<string> &grid) {
// Process the grid from right to left
// cout << "Height: " << height << ", Width: " << width << ", N: " << n << endl;
for (int i = 0; i < height; i++) {
for (int j = width - 1; j >= 0; j--) {
if (grid[i][j] == 'X') {
break;
}
if (grid[i][j] == '.') {
continue;
}
// cout << "I: " << i << ", J: " << j << ", Val: " << grid[i][j] << endl;
vector<string> gridCopy = grid;
bool ans = isObstructued(i, j, grid[i][j], gridCopy);
if (ans) {
int copy = grid[i][j] - '0';
// cout << grid[i][j] << " " << i << " " << j << endl;
exitBlock(i, j, grid[i][j], grid);
// cout << "Found something useful" << endl;
// cout << copy << endl;
return copy;
} else {
break;
}
}
}
return -1;
}
void printGrid(vector<string> &grid) {
for (auto &s: grid) {
cout << s << endl;
}
cout << endl;
}
int main() {
vector<TestCase> testCases = {
// Test Case 1: Single Piece Without Obstruction
{
5, 4, 1, {
".....",
".000.",
".....",
"....."
}, 0
},
// Test Case 2: Single Piece With Obstruction
{
6, 4, 1, {
"......",
".000.X",
"......",
"......"
}, -1
},
// Test Case 3: Multiple Pieces
{
7, 4, 2, {
".......",
".11111.",
".2222X.",
"......."
}, 1
},
// Test Case 4: Piece Touching the Edge
{
5, 3, 1, {
".....",
"....0",
"....."
}, 0
},
// Test Case 5: Complex Grid
{
8, 5, 3, {
"........",
".111....",
".2222XX.",
".3333...",
"........"
}, 1
},
// Test Case 6: Fully Obstructed Grid
{
5, 4, 2, {
"XXXXX",
"X000X",
"X000X",
"XXXXX"
}, -1
},
{
6, 5, 2, {
"......",
"..111.",
"..1.2.",
"..1.2.",
"......"
}, -1
},
{
7, 6, 3, {
".......",
".11122.",
"..1.2..",
"..1.2..",
"...333.",
"......."
}, -1
},
{
8, 7, 4, {
"........",
"..11122.",
"..1..2..",
".333.2..",
"...3.444",
"....444.",
"........"
}, -1
},
{
6, 6, 3, {
"......",
".111..",
".1.222",
".1.2..",
".333..",
"......"
}, -1
},
{
11, 8, 5, {
"...........",
".11111.....",
"..2..1.....",
"..222.333..",
"...2.3.....",
"..4444.3...",
"...555.....",
"..........."
}, -1
},
{
7, 7, 2, {
".......",
".1111..",
"..2XX..",
"..2XX..",
".1111..",
".......",
"......."
}, -1
},
{
9, 7, 4, {
".........",
"..111....",
"..1.222..",
"..1.2.3..",
"...3333..",
"...4.....",
"...4444.."
}, -1
},
{
11, 8, 5, {
"...........",
"..11111....",
"..1..2.....",
"..1..222...",
"..1...3....",
"..44443....",
"...555.....",
"..........."
}, -1
},
{
11, 7, 4, {
"...........",
"..11111....",
"..1..X.....",
"..1..222...",
"..1...3....",
"..44443....",
"...X......."
}, -1
},
{
13, 10, 6, {
".............",
"....11111....",
"....1....22..",
"...33333..2..",
"...3....44...",
"...3..5555...",
"....6666.....",
"....6........",
".............",
"............."
}, -1
},
{
12, 12, 6, {
"............",
"...1111.....",
"...1.X..22..",
"...1.X..2...",
"...1..3333..",
"....444.....",
"..55555.....",
"...6...66...",
"...6666.....",
"...X........",
"............",
"............"
}, -1
}
};
// Iterate through the test cases and run the solve function
for (size_t i = 0; i < testCases.size(); ++i) {
TestCase test = testCases[i];
cout << "Test Case " << (i + 1) << endl;
printGrid(test.grid);
int res;
do {
res = solve(test.height, test.width, test.nbBlocks, test.grid);
cout << res << endl;
} while (res != -1);
cout << "**************************************" << endl;
// cout << "Expected Output: " << test.expectedOutput << ", ";
// cout << "Actual Output: " << result << endl;
// if (result == test.expectedOutput) {
// cout << "Test Case Passed ✅" << endl;
// } else {
// cout << "Test Case Failed ❌" << endl;
// }
}
return 0;
}
// int main() {
// int width = 4;
// int height = 5;
// int nbBlocks = 3;
// // Simple Test Case
// vector<string> testCase = {
// "XXXX",
// "X000",
// "X111",
// "X222",
// "XXXX"
// };
// int result = solve(height, width, nbBlocks, testCase);
// cout << result << endl;
// result = solve(height, width, nbBlocks, testCase);
// cout << result << endl;
// result = solve(height, width, nbBlocks, testCase);
// cout << result << endl;
// }
Editor is loading...
Leave a Comment