# 12615 - Knight Search
## 題解:
DFS
(a−c)^2 + (b−d)^2 = 5代表有八個方向要去檢查，
看八個位置如果有符合s的話，就繼續搜下去。
## Code:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define N 100 + 5

int n;
char m[N][N]; // chess land
char s[] = "ICPCASIASG";

bool dfs(int x, int y, int pos){
    if(pos == strlen(s))
        return true;
    int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
    int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
    for(int i=0; i<8; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx<0 || nx>=n || ny<0 || ny>=n)
            continue;
        if(m[nx][ny] == s[pos])
            if(dfs(nx, ny, pos + 1))
                return true;
    }
    return false;
}

int main(){
    scanf("%d\n", &n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            scanf("%c", &m[i][j]);
    bool flag = false;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(dfs(i, j, 0))
                flag = true;
    printf(flag ? "YES\n" : "NO\n");
    return 0;
}

###### tags: `NTHUOJ`