로곡 P1002하수인dp 패스 수

3126 단어
제목 대의: 바둑판 n*m에서 졸기점(0,0)은 아래로 또는 오른쪽으로만 갈 수 있고 종점(n,m)까지 가야 한다. (hx,hy)에 말이 하나 있다. 말이 가는 날, 말에 의해 제어된 칸도 갈 수 없다. nm hxhy를 입력하고 졸의 모든 경로 개수를 묻는다.
mark[][] 마커 제어의 격자 dp[i][j]는 (i, j)점까지 가는 경로를 표시하고 0으로 초기화하며 dp[0][0]는 1로 초기화합니다.상태 이동 방정식: dp[i][j]+=dp[i-1][j], dp[i][j]+=dp[i][j-1]

#include 

using namespace std;

typedef long long LL;

int nx, ny, hx, hy;
LL dp[21][21] = {1};
bool mark[21][21] = {0};

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int main()
{
    int i, j;
    scanf("%d %d %d %d", &nx, &ny, &hx, &hy);
    mark[hx][hy] = 1;
    for(i = 0; i < 8; ++i)
        if(hx+dx[i]>=0 && hx+dx[i]<=nx && hy+dy[i]>=0 && hy+dy[i]<=ny)
            mark[hx+dx[i]][hy+dy[i]] = 1;
    for(i = 0; i <= nx; ++i)
        for(j = 0; j <= ny; ++j)
    {
        if(mark[i][j]) continue;
        if(i) dp[i][j] += dp[i-1][j];
        if(j) dp[i][j] += dp[i][j-1];
    }
    printf("%lld
"
, dp[nx][ny]); return 0; }

좋은 웹페이지 즐겨찾기