Trong bài toán này, chúng ta được cung cấp một mảng 2d đại diện cho màn hình 2-D, tọa độ của một pixel trên màn hình sẽ được tô màu và màu sắc. Nhiệm vụ của chúng tôi là tạo một chương trình để Tô màu cho pixel hiện tại và tất cả các pixel lân cận có màu đó.
Tô màu bằng sơn , chúng tôi sẽ chọn một màu và nhấp vào pixel đã cho với sự mài mòn.
Hãy lấy một ví dụ để hiểu vấn đề
Input: Sceen[][] =
{{W, W, B, W, W, W, W, W},
{W, W, W, W, W, W, B, B},
{W, B, B, W, W, B, W, W},
{W, Y, Y, Y, Y, B, W, B},
{B, W, W, Y, Y, B, W, B},
{B, W, W, Y, Y, Y, Y, B},
{W, B, W, W, W, Y, W, W},
{W, W, B, B, W, Y, Y, W}};
X = 5, Y = 5, newColor = R.
Output:
{{W, W, B, W, W, W, W, W},
{W, W, W, W, W, W, B, B},
{W, B, B, W, W, B, W, W},
{W, R, R, R, R, B, W, B},
{B, W, W, R, R, B, W, B},
{B, W, W, R, R, R, R, B},
{W, B, W, W, W, R, W, W},
{W, W, B, B, W, R, R, W}}; Thuật toán lấp đầy lũ
Trong thuật toán này, các pixel sẽ được tô bằng màu mới khi nó đã có màu trước đó được chọn. Nếu màu trước đó không phải là màu trước đó, pixel đó sẽ không được tô. Sau khi điền vào một pixel, nó sẽ kiểm tra các pixel lên, xuống, trái và phải của nó để thực hiện tương tự. Tìm hiểu thêm tại đây.
Phương pháp tiếp cận giải pháp
Một phương pháp để giải quyết vấn đề là sử dụng cách tiếp cận đệ quy. Chúng ta sẽ tìm quả thông đầu tiên mà chúng ta cần tô màu, sau đó kiểm tra tất cả 4 điểm ảnh lân cận của nó. Phù hợp với cùng một màu sau đó thay thế nó bằng màu mới và lặp lại với các vùng lân cận của pixel hiện tại. Nếu pixel lân cận có bất kỳ màu nào khác, hãy bỏ nó đi. Làm theo các bước sau cho đến khi bạn nhận được tất cả các quả thông liền kề có cùng màu với pixel bắt đầu được tô màu. Sau đó dừng thuật toán điền.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include<iostream>
using namespace std;
#define M 8
#define N 8
void fillColorAdj(char screen[][N], int x, int y, char oldColor, char color){
if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (screen[x][y] != oldColor)
return;
if (screen[x][y] == color)
return;
screen[x][y] = color;
fillColorAdj(screen, x+1, y, oldColor, color);
fillColorAdj(screen, x-1, y, oldColor, color);
fillColorAdj(screen, x, y+1, oldColor, color);
fillColorAdj(screen, x, y-1, oldColor, color);
}
void fillColor(char screen[][N], int x, int y, char color){
char oldColor = screen[x][y];
if(oldColor==color) return;
fillColorAdj(screen, x, y, oldColor, color);
}
int main(){
char screen[M][N] = {{'W', 'W', 'B', 'W', 'W', 'W', 'W', 'W'},
{'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B'},
{'W', 'B', 'B', 'W', 'W', 'B', 'W', 'W'},
{'W', 'Y', 'Y', 'Y', 'Y', 'B', 'W', 'B'},
{'B', 'W', 'W', 'Y', 'Y', 'B', 'W', 'B'},
{'B', 'W', 'W', 'Y', 'Y', 'Y', 'Y', 'B'},
{'W', 'B', 'W', 'W', 'W', 'Y', 'W', 'W'},
{'W', 'W', 'B', 'B', 'W', 'Y', 'Y', 'W'},};
int x = 5, y = 5;
char color = 'R';
cout<<"The initial screen cordinates are : \n";
for (int i=0; i<M; i++){
for (int j=0; j<N; j++)
cout<<screen[i][j]<<"\t";
cout<<endl;
}
fillColor(screen, x, y, color);
cout<<"\nThe screen cordinates after coloring are : \n";
for (int i=0; i<M; i++){
for (int j=0; j<N; j++)
cout<<screen[i][j]<<"\t";
cout<<endl;
}
} Đầu ra
The initial screen cordinates are : W W B W W W W W W W W W W W B B W B B W W B W W W Y Y Y Y B W B B W W Y Y B W B B W W Y Y Y Y B W B W W W Y W W W W B B W Y Y W The screen cordinates after coloring are : W W B W W W W W W W W W W W B B W B B W W B W W W R R R R B W B B W W R R B W B B W W R R R R B W B W W W R W W W W B B W R R W