[백준 15683] 감시 (순열) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[10][10];
int direct[10];
int N, M;
int Min = 99999999;
 
int cctv[10];
int cctvCnt;
pair<int, int> cctvPos[10];
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1}; // 상하좌우 
 
void copy(int mapCopy[10][10])
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            mapCopy[i][j] = map[i][j];
        }
    }
}
 
void back_up(int mapCopy[10][10])
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            map[i][j] = mapCopy[i][j];
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < M)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int zeroCount()
{
    int cnt = 0;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(map[i][j] == 0)
            {
                cnt++;        
            }
        }
    }
    
    return cnt;
}
 
void cctv1(int x, int y, int dir)
{
    while(1)
    {
        int xpos = x+dx[dir];
        int ypos = y+dy[dir];
            
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
        {
            map[xpos][ypos] = 7;
            x = xpos;
            y = ypos;
        }
        else
        {
            break;
        }
    }    
} 
 
void cctv2(int x, int y, int dir)
{    
    if(dir == 0 || dir == 1) // 상하 
    {
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 2 || dir == 3) // 좌우 
    {
        for(int i = 2; i < 4; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
} 
 
void cctv3(int x, int y, int dir)
{
    if(dir == 0) // ㄴ모양 
    {
        int dx[2] = {-1, 0}; // 상우 
        int dy[2] = {0, 1};  // 상우
         
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 1) //「 모양 
    {
        int dx[2] = {0, 1};  // 우하 
        int dy[2] = {1, 0};  // 우하 
        
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 2) // ㄱ모양 
    {
        int dx[2] = {0, 1};  // 좌하 
        int dy[2] = {-1, 0}; // 좌하 
        
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 3) // 」모양 
    {
        int dx[2] = {-1, 0}; // 상좌 
        int dy[2] = {0, -1}; // 상좌 
        
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
} 
 
void cctv4(int x, int y, int dir)
{
    if(dir == 0) // ㅗ모양 
    {
        int dx[3] = {-1, 0, 0}; // 상좌우 
        int dy[3] = {0, -1, 1}; // 상좌우 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 1) // ㅏ모양 
    {
        int dx[3] = {-1, 1, 0}; // 상하우 
        int dy[3] = {0, 0, 1};  // 상하우 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 2) // ㅜ모양 
    {
        int dx[3] = {0, 0, 1};  // 좌우하 
        int dy[3] = {-1, 1, 0}; // 좌우하 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }        
        }
    }
    else if(dir == 3) // ㅓ모양 
    {
        int dx[3] = {-1, 1, 0}; // 상하좌 
        int dy[3] = {0, 0, -1};  // 상하좌 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
} 
 
void cctv5(int x, int y, int dir)
{
    for(int i = 0; i < 4; i++)
    {
        int tempx = x;
        int tempy = y;
        
        while(1)
        {
            int xpos = tempx+dx[i];
            int ypos = tempy+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
            {
                map[xpos][ypos] = 7;
                tempx = xpos;
                tempy = ypos;
            }    
            else
            {
                break;
            }
        }    
    }
}
 
void execute_cctv(int cnt)
{
    if(cctv[cnt] == 1)
    {
        cctv1(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 2)
    {
        cctv2(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 3)
    {
        cctv3(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 4)
    {
        cctv4(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 5)
    {
        cctv5(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
}
 
void permutation(int cnt)
{
    if(cnt == cctvCnt)
    {    
        // print
//        for(int i = 0; i < N; i++)
//        {
//            for(int j = 0; j < M; j++)
//            {
//                cout << map[i][j] << " ";
//            }
//            cout << endl;
//        }
//        cout << endl;
        
        int val = zeroCount();
        
        if(val < Min)
        {
            Min = val;
            // print
//            cout << Min << endl;
//            for(int i = 0; i < N; i++)
//            {
//                for(int j = 0; j < M; j++)
//                {
//                    cout << map[i][j] << " ";
//                }
//                cout << endl;
//            }
//            cout << endl;
        }
        
        return;
    }
    
    // 방향에 대한 중복순열 (0 ~ 4 // 0, 90, 180, 270) 
    for(int i = 0; i < 4; i++)
    { 
        int mapCopy[10][10];
        copy(mapCopy);
        
        direct[cnt] = i;
        execute_cctv(cnt);
        permutation(cnt+1);
    
        back_up(mapCopy);
    }
}
 
int main(void)
{
//    freopen("B15683_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &M);    
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
                
            if(map[i][j] != 0 && map[i][j] != 6)
            {
                cctv[cctvCnt] = map[i][j];
                cctvPos[cctvCnt].first = i;
                cctvPos[cctvCnt++].second = j;
            }
        }
    } 
    
    permutation(0);
    
    printf("%d", Min);
    
    return 0;
}