백준 1331 나이트 투어

• 문제 URL : https://www.acmicpc.net/problem/1331

1331번: 나이트 투어

 

• 문제 접근법 : 나이트의 이동방향 총 8가지입니다 아래 그림처럼 

나이트의 이동방향

• 현재 방향과 이전방향의 차이를 구한다음 저8가지가 일치하는것이 있다면 나이가 움직이는 이동방향이고 아니면 나이트로서 움직인것이 아닙니다
• 마지막으로 밟았던자리를 다시밟지않고 마지막 밟은곳과 처음으로 이동한곳의 이동방향이 나이트이동방향인지 확인해야합니다 이유는 제자리로 돌아올수있는지 확인하기위해

소스코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

//By 콩순이냉장고 #include <bits/stdc++.h> using namespace std; vector<string> v(36); int dy[8] = { -2,-1,1,2,2,1,-1,-2 }; int dx[8] = { 1,2,2,1,-1,-2,-2,-1 }; void input() {     for (int i = 0; i < 36; i++){         cin >> v[i];     } } //범위인지 bool isrange(int y, int x) {     return 0 <= y && y < 6 && 0 <= x && x < 6; }   //나이트의 방향이 맞는지 bool check(int y,int x,int by,int bx){     for (int i = 0; i < 8; i++) {         int diry = y - by;         int dirx = x - bx;         if (dy[i] == diry && dx[i] == dirx)return true;     }     return false; }   void solve() {     bool visit[6][6] = { 0 };     int by = v[0][0] - 'A';     int bx = v[0][1] - '1';     int fy = by;     int fx = bx;     if (!isrange(by, bx)) {         cout << "Invalid\n";         return;     }     visit[by][bx] = 1;       for (int i = 1; i < v.size(); i++) {         int y = v[i][0] - 'A';         int x = v[i][1] - '1';         if (isrange(y, x) && !visit[y][x] && check(y, x, by, bx)) {             visit[y][x] = 1;             by = y;             bx = x;         }         else {             cout << "Invalid\n";             return;         }     }          //마지막에 현재로 돌아올수있는지 까지 체크     cout << (check(fy, fx, by, bx) ? "Valid\n" : "Invalid\n");    }     int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     //freopen("input.txt", "r", stdin);     input();     solve();     return 0; } Colored by Color Scripter

cs

 

궁금한점 혹은 모르는점 혹은 논리적인 오류등 댓글은 언제든지 환영입니다.