[NOIP2002 普及组] 过河卒

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型 棋盘行数
# @param m int整型 棋盘列数
# @param x int整型 马的横坐标
# @param y int整型 马的纵坐标
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/8439d41faa254418a3146c8cc0a68d62?tpId=196&tqId=40500&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        1. 根据马的坐标(x, y)，计算马的所有控制点坐标，写入attack，我们将这些点视为障碍物
        2. 问题转化为在有障碍物的矩阵中，从左上角 -> 右下角的路径总和
        设dp[i][j]表示到达位置(i, j)的路径总和
        若(x, y) == (0, 0) # 即马出现在左上角，直接返回0
        初始化：
            dp[0][0] = 1
        状态转移方程：
            dp[0][j] = dp[0][j-1] if (0, j) not in attack else 0
            dp[i][0] = dp[i - 1][0] if (i, 0) not in attack else 0
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] if (i, j) not in attack
        返回值：
            dp[-1][-1]
    复杂度：
        时间复杂度：O((n+1)*(m+1)) = O(nm), n, m分别为终点的行坐标和列坐标
        空间复杂度：O((n+1)*(m+1)) = O(nm)
    """

    def crossRiver(self, n, m, x, y):
        # write code here
        if x == 0 and y == 0:
            return 0

        attack = {(x, y), (x - 2, y - 1), (x - 2, y + 1), (x - 1, y - 2), (x - 1, y + 2),
                (x + 1, y - 2), (x + 1, y + 2), (x + 2, y - 1), (x + 2, y + 1)} # 马走日，枚举马的攻击范围，这里我们无需考虑是否存在越界的无效攻击点，无效的攻击点，只是占用了O(1)的空间而已。

        if (0, 0) in attack: # 出发点在马的攻击范围内
            return 0

        # print attack

        dp = [[0] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1): # 第0列处理：只能由上方的坐标到达，若(i, 0)属于马的攻击范围，那么后面的点都无法到达，无需接着遍历
            if (i, 0) in attack:
                break
            dp[i][0] = dp[i-1][0]

        for j in range(1, m + 1): # 第0行处理：只能由左方的坐标到达，若(0, j)属于马的攻击范围，那么后面的点都无法到达，无需接着遍历
            if (0, j) in attack:
                break
            dp[0][j] = dp[0][j-1]

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if (i, j) in attack:
                    continue
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        # print dp

        return dp[-1][-1] #&nbs***bsp;dp[n][m]

if __name__ == "__main__":
    sol = Solution()

    # n, m, x, y = 6, 6, 3, 3

    # n, m, x, y = 5, 4, 2, 3

    n, m, x, y = 2, 5, 3, 5

    res = sol.crossRiver(n, m, x, y)

    print res