BOJ 18224

#include <iostream>
#include <queue>
#include <cstring>
#include <math.h>
using namespace std;
#define MAXN 501

struct node{
    int x;
    int y;
    int flag;
    int cnt;
};
bool visited[MAXN][MAXN][2][11];
int map[MAXN][MAXN];
int N,M;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
queue<node> q;
bool is_range(int x, int y){
    return (x>=0 && y >= 0 && x <N && y <N);
}
pair<int,int> bfs(){

    q.push({0,0,0,1});
    visited[0][0][0][1] = true;
    while (!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int cnt = q.front().cnt;
        int flag = q.front().flag;
        q.pop();
        if (x == N-1 && y == N-1){
            return {flag,(int)ceil((double)cnt/(M*2))};
        }
        for (int k = 0; k< 4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (!is_range(nx,ny)) continue;
            int next_state = (int)ceil((double)(cnt+1)/M) % 2==1 ? 0 : 1;
            int next_cnt = (cnt+1)%M;
            if (visited[nx][ny][next_state][next_cnt]) continue;
            // 현재 상태가 낮일 경우
            if (!flag){
                if (map[nx][ny]) continue;
                visited[nx][ny][next_state][next_cnt] = true;
                q.push({nx,ny,next_state,cnt+1});
            }
            // 현재 상태가 밤일 경우
            else{
                if (map[nx][ny]){
                    while (map[nx][ny]){
                        nx += dx[k];
                        ny += dy[k];
                    }
                    if (!is_range(nx,ny) || 
                    visited[nx][ny][next_state][next_cnt])
                    continue;
                    visited[nx][ny][next_state][next_cnt] = true;
                    q.push({nx,ny,next_state,cnt+1});
                }
                else{
                    visited[nx][ny][next_state][next_cnt] = true;
                    q.push({nx,ny,next_state,cnt+1});
                }
            }
        }
    }
    return {-1,-1};
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;

    for (int i =0 ; i < N; i++){
        for (int j =0;j<N; j++){
            cin >> map[i][j];
        }
    }
    pair<int,int> ans = bfs();
    if (ans.second == -1) cout <<"-1\n";
    else{
        cout << ans.second <<" ";
        if (ans.first== 0) cout << "sun\n";
        else cout <<"moon\n";
    }
    return 0;
}