Loading Now

[STLC++Queue]rotOrange

Cpp STL Queue

Bài tập.

Cho một ma trận trong đó mỗi ô trong ma trận có thể có các giá trị 0, 1 hoặc 2 có nghĩa sau:

  • 0: Là một ô trống.
  • 1: Là một quả cam tươi.
  • 2: Là một quả cam bị hỏng.

Chúng ta phải xác định thời gian tối thiểu mà  tất cả các quả cam bị hỏng. Một quả cam hỏng ở chỉ số [i, j] có thể làm hỏng quả cam tươi khác ở các chỉ số [i-1, j], [i + 1, j], [i, j-1], [i, j + 1] (lên , xuống, trái và phải). Nếu không thể bị hỏng tất cả quả cam thì trả về -1.

Ví dụ:

  • Với matrix = [
    [2, 1, 0, 2, 1],
    [1, 0, 1, 2, 1],
    [1, 0, 0, 2, 1]].
    Thì đầu ra có dạng  rotOrange(matrix) = 2

  • Với matrix = [
    [2, 1, 0, 2, 1],
    [0, 0, 1, 2, 1],
    [1, 0, 0, 2, 1]].
    Thì đầu ra có dạng rotOrange(matrix) = -1

Hướng dẫn.

Sử dụng tìm kiếm theo chiều rộng (Bfs).

Code mẫu:

int rotOrange(std::vector<std::vector<int>> matrix)
{
    queue <int> x,y;  
  	int now = 0, next = 0, pas = 0, res = 0;
    int ans = 0; 
    for (int  i = 0; i < matrix.size(); i++)
    {
        for (int j = 0; j < matrix[i].size(); j++)
        {
            if(matrix[i][j] == 2)
            {
                x.push(i);
                y.push(j);
                now ++;
                matrix[i][j] = 0;
            }
            else if (matrix[i][j] == 1)
            	res ++;
    	}
	}
    while (!x.empty())
    {
        now--;
        int o[] = {0, 1, 0, -1};
        int p[] = {1,0, -1 ,0};
        for (int d = 0; d < 4; d++)
        {
            if( x.front()+o[d] >= 0 && x.front()+o[d] < matrix.size() &&  y.front()+p[d] >= 0 && y.front()+p[d] < matrix[1].size() && matrix[x.front()+o[d]][y.front()+p[d]] == 1 )
            {
                matrix[x.front()+o[d]][y.front()+p[d]] = 0;
                x.push(x.front()+o[d]);
                y.push(y.front()+p[d]);
                matrix[x.front()+o[d]][y.front()+p[d]]= 0;
                res --;
                next++;
            }
        }
        if(now == 0 && next > 0)
        {
            now = next;
            next = 0;
            pas ++;
        }
        x.pop();
        y.pop();
        
    }
    if (res == 0){
        return pas;
    } else {
        return -1;
    } 
}

Post Comment

Contact