Shopee 2019校招部分程式設計題彙總（C++解法）

第一題：[程式設計題]Shopee的辦公室（二）

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 32M，其他語言64M

題目描述：

shopee的辦公室非常大，小蝦同學的位置坐落在右上角，而大門卻在左下角，可以把所有位置抽象為一個網格（門口的坐标為0，0），小蝦同學很聰明，每次隻向上，或者向右走，因為這樣最容易接近目的地，但是小蝦同學不想讓自己的boss們看到自己經常在他們面前出沒，或者遲到被發現。他決定研究一下如果他不通過boss們的位置，他可以有多少種走法？

輸入描述:

第一行 x,y,n (0<x<=30, 0<y<=30, 0<=n<= 20) 表示x,y小蝦的座位坐标,n 表示boss的數量（ n <= 20）

接下來有n行, 表示boss們的坐标(0<xi<= x, 0<yi<=y，不會和小蝦位置重合)

x1, y1

x2, y2

……

xn, yn

輸出描述

輸出小蝦有多少種走法

輸入例子1:

3 3 2
1 1
2 2
           

輸出例子1:

動态規劃法

思路：用一張二維數組表存儲小蝦同學的位置和boss們的位置，其中小蝦同學位置标記為 1，boss們的位置标記為 -1，其餘的位置标記為 0。根據題目意思，推導出動态規劃公式如下：

mark[ i ] [ j ] = max ( mark[ i + 1 ] [ j ], 0) + max ( mark[ i ] [ j + 1], 0), 其中 0 <= i <= x, 0 <= j <= y;

從小蝦同學位置 (x, y) 逆向出發，到（0,0）位置結束。先向上走，再向左走，其中遇到boss位置則跳過，否則對目前位置執行上述公式，目的就是儲存每一個點到達(x, y)位置的路徑總和。因為小蝦同學隻能向下和向右走，是以隻需儲存目前位置（mark[i][j]）的右邊位置（mark[ i + 1 ] [ j ]）和下邊位置（mark[ i ] [ j + 1]）到達(x, y)的路徑總和，一路周遊累加下來，mark(0, 0)的值即為最終結果。代碼如下：

#include<iostream>
#include<algorithm>
using namespace std;

long long mark[32][32];

int main() {
    int x, y, n;
    cin >> x >> y >> n;
    for (int i = 0; i < n; ++i) {
    	/*二維表存儲boss們的位置*/
        int tmpX, tmpY;
        cin >> tmpX >> tmpY;
        mark[tmpX][tmpY] = -1;
    }
    mark[x][y] = 1;		/*小蝦同學位置标記為1*/
    for (int i = x; i >= 0; --i)
        for (int j = y; j>= 0; --j) {
            if (mark[i][j] == -1 || (i == x && j == y))
                continue;
            mark[i][j] = max(mark[i + 1][j], (long long)(0))
                + max(mark[i][j + 1], (long long)(0));
        }
    cout << mark[0][0] << endl;
    return 0;
}