백준(BOJ) 11084 나이트의 염탐 **

bfs 문제였습니다.

저는 몇 가지 실수를 해서................. 오래 걸렸지만.........

그렇게 어려운 문제는 아닌 것 같습니다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 405
#define INF 987654321
#define MOD 1000000009
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int mx, my, x, y, ans = INF;
bool visit[MAX][MAX];
pi dp[MAX][MAX];
queue<pi> q;
int dx[8] = { 2,2,1,-1,-2,-2,1,-1 }, dy[8] = { -1,1,2,2,1,-1,-2,-2 };
// bfs를 기존에 많이 쓰는 4방향이 아닌 8방향에 대해서 준비한다.

int main()
{
	scanf("%d%d", &my, &mx);
	visit[1][1] = true;
	dp[1][1].second = 1;
	q.push(make_pair(1, 1));
	// 처음 노드를 넣어준다.

	while (!q.empty())
	{
		x = q.front().first, y = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++)
		// 8방향에 대해서 돌려준다.
		{
			int tmp_x = x + dx[i], tmp_y = y + dy[i];
			if ((1 <= tmp_x && tmp_x <= mx) && (1 <= tmp_y && tmp_y <= my))
			{
				if (visit[tmp_y][tmp_x] == false || dp[tmp_y][tmp_x].first == dp[y][x].first + 1)
				{
					dp[tmp_y][tmp_x].second = (ll)(dp[tmp_y][tmp_x].second + dp[y][x].second) % MOD;
					// 가짓수를 갱신해준다.
					if (visit[tmp_y][tmp_x] == false)
					// 첫 방문일때
					{
						dp[tmp_y][tmp_x].first = dp[y][x].first + 1;
						// 이동한 거리를 갱신해준다.
						q.push(make_pair(tmp_x, tmp_y));
						visit[tmp_y][tmp_x] = true;
					}
				}
			}
		}
	}
	if (dp[my][mx].second == 0)
		printf("None\n");
	else
		printf("%d %d\n", dp[my][mx].first, dp[my][mx].second);
	return 0;
}