[코드포스 Practice12] B. New Year and Buggy Bot

코포 시간 내에 못 풀고 끝나고 다시 풀었다

 

이 문제를 복잡하게 생각해서 백트래킹을 써야하나??? 생각했는데 시간복잡도를 계산해보니 얼마 안 된다. 그래서 완전탐색으로 풀었다. 

 

알고리즘까지는 바로 구현했는데 udlr 4!번 비교하는 데서 문제였다. 4! 섞어서 비교하는데?? 이거랑 mv 문자열이랑 비교를 어떻게 하지?? 싶었지만 어찌저찌 해결했다. 

 

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

int main()
{
    int n, m;
    int s_i, s_j;
    cin >> n >> m;
    vector<string> arr(n);
    string mv;
    string udlr = "0123";
    int ans = 0;

    //input
    sort(udlr.begin(), udlr.end());
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 'S')
            {
                s_i = i;
                s_j = j;
            }
        }
    }
    cin >> mv;
    
    //main code
    do 
    {
        int now_i = s_i, now_j = s_j;
        for (int i = 0; i < mv.size(); i++)
        {
            if (mv[i] == udlr[0])
                now_i--;
            if (mv[i] == udlr[1])
                now_i++;
            if (mv[i] == udlr[2])
                now_j--;
            if (mv[i] == udlr[3])
                now_j++;
            if (now_i < 0 || n <= now_i || now_j < 0 || m <= now_j)
                break;
            if (arr[now_i][now_j] == '#')
                break;
            if (arr[now_i][now_j] == 'E')
            {
                ans++;
                break;
            }
        }
    } while (next_permutation(udlr.begin(), udlr.end()));
    
    printf("%d", ans);
}