注意事項

何回解けますか?

ポリシー

dfs(??)
{
	//벽 설치하는 카운팅
    //~~~~
    
    for(int i ~ 세로 길이)
    {
    	for(int j ~ 가로 길이 )
        {
        	if(arr[i][j] == 0)
            {
            	arr[i][j] = 1;
            	cnt += 1;
            
            	//이런식으로 해야만, arr[i][j] 가 0으로 놓고 탐색이 가능한 것이다. 
            	dfs();
                
                arr[i][j] = 0;
            	cnt -= 1;
            }
        }
        
   	}
    
    

}

考える部分

最初のコード

ウイルスは一度に拡散し、論理的には目標点の上下左右に拡散する.感染した場所があれば、感染した場所をターゲットに拡散する方法でコードを変更します.

->これを使えば例1が正しいが,残りは間違っている.

最終コード

ソースコード

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int n, m;
int cnt = 0;
vector<vector<int>>tmp;
vector<vector<int>>v;

int answer = 0;


//상하좌우 
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

void virus(int y, int x)
{
	//상하좌우를 재귀로 처리하자. 

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || ny >= n
			|| nx < 0 || nx >= m)
			continue;

		if (tmp[ny][nx] == 0)
		{
			tmp[ny][nx] = 2;
			virus(ny, nx);
		}
	}

	

}


void backTracking()
{
	//바이러스 확산하자.
	if (cnt == 3)
	{
		tmp = v;
		//2일 때만 판단해서 virus 함수 호출하자.
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (tmp[i][j] == 2)
				{
					virus(i, j);
				}
			}
		}

		int result = 0;
		//바이러스 확산 완료 후에 카운팅하자. 
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (tmp[i][j] == 0)
				{
					result += 1;
				}
			}
		}

		answer = max(answer, result);
		return;
	}

	//벽은 1, 바이러스는 2, 빈 공간은 0
	//벽을 3개 세우면서 백트래킹 처리하자. 
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (v[i][j] == 0)
			{
				v[i][j] = 1;
				cnt += 1; 

				backTracking();

				v[i][j] = 0;
				cnt -= 1;
			}
		}
	}


}


int main()
{
	//벽 3개를 모두 세운뒤에 바이러스 확산 후에 
	//min값 계산하자.
	
	cin >> n >> m;

	v.resize(n, vector<int>(m));	
	

	//0은 빈칸, 1은 벽, 2는 바이러스이다. 

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> v[i][j];
		}
	}

	backTracking();

	cout << answer; 

	

}