BOJ::17836 공주님을 구해라!

[BOJ] : https://www.acmicpc.net/problem/17836

시사점

이해(3)

설계(2)

시간 복잡도

공간 복잡도

구현(5)

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 100;
const int INF = 987654321;
struct cell{int x; int y; int mv;};
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};

int n, m, mxmv;
int sx, sy, ex, ey;

int a[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
queue<cell> q; // x, y, mv
bool over(int x, int y){return (x<0 || y<0 || x>=n || y>=m);}
void solve(){
    int ret = INF;
    visited[sx][sy] = true;
    q.push({sx, sy, 0});
    while(!q.empty()){
        int x = q.front().x, y = q.front().y, mv = q.front().mv; q.pop();
        if(x == ex && y == ey){
            ret = min(ret, mv);
            continue;
        }
        for(int i = 0; i < 4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(over(nx, ny) || visited[nx][ny] || a[nx][ny] == 1) continue;
            visited[nx][ny] = true;
            if(a[nx][ny] == 0){
                q.push({nx, ny, mv+1});
            }else{
                int dist = abs(nx - ex) + abs(ny - ey);
                ret = min(dist + 1 + mv, ret);
            }
        }
    }
    if(ret <= mxmv)cout << ret <<"\n";
    else cout << "Fail\n";
}
int main(){
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> mxmv;
    sx = 0, sy = 0, ex = n-1, ey = m-1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> a[i][j];
    solve();
    return 0;
}

디버깅(x)

좋은 코드

최적화