首页 > 试题广场 >

Shopee的办公室（二）

[编程题]Shopee的办公室（二）
  • 热度指数：9259 时间限制：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

输出

4
算法知识视频讲解
添加回答
Python
sky游荡头像 sky游荡
玛德，开始推反了，想错了，一直过50%贼气。 
x,y,n = map(int,input().split())
dpc = [[1 for j in range(y+1)]for j in range(x+1)]
for _ in range(n):
    i,j = map(int,input().split())
    dpc[i][j] = 0
for i in range(1,x+1):
    for j in range(1,y+1):
        if dpc[i][j]!=0:
            dpc[i][j] = dpc[i-1][j]+dpc[i][j-1]
print(dpc[-1][-1])


发表于 2020-04-22 21:38:36 回复(0)
Gelivabilities头像 Gelivabilities 
[x,y,n]=[int(t) for t in input().split()]
M=[[1 for j in range(y+1)]for i in range(x+1)]
for i in range(n):
    [a,b]=[int(t) for t in input().split()]
    M[a][b]=0
 
def myfun(M,x,y):
    for i in range(x+1):
        for j in range(y+1):
            if M[i][j]==0 or (i==0 and j==0):continue
            M[i][j]=(0 if i==0 else M[i-1][j])+(0 if j==0 else M[i][j-1])
    return M[x][y]
 
print(myfun(M,x,y))

发表于 2019-06-28 18:49:22 回复(0)
Java
Mr.X-Ray头像 Mr.X-Ray

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int boss_num = sc.nextInt();
        //与其用数组去维护boss的坐标位置，不如直接在表里填-1，表示不可走
        long[][] mv = new long[x+1][y+1];//因为从0开始到y，所以空间是y+1;
        for(int i=0;i<boss_num;i++) {
            mv[sc.nextInt()][sc.nextInt()]=-1;
        }
        long res = count_mv(x,y,mv);
        System.out.println(res);
    }
    // 思路：维系一个动态规划表，表格下标代表位置
    //当自己的位置在（i，j)时候，走法一共有 mv[i][j]=mv[i][j-1]+mv[i-1][j]
    //因为都表示只差一步就到（i,j)，所以情况相加就行
    //考虑到对称性，决定只填上三角形，"但这是不对"！,只填上三角形存在一种情况，上一行那个数是老板位置为0,你无法*2
    //会漏掉前一列可以行走的可能性！
    //因此需要初始化第一行来符合上面的公式，
    private static long count_mv(int x, int y,long[][] mv) {
        //初始化
        for(int i=0;i<=y;i++) {
            mv[0][i]=1;//在同一行的时候，只有1种情况，右移
        }
        for(int i=0;i<=x;i++) {
            mv[i][0]=1;//同一列只有一种情况
        }
        //填表，按行、上三角形填
        for(int i=1;i<=x;i++) {
            for(int j=1;j<=y;j++) {
                if(mv[i][j] == -1) mv[i][j]=0; //老板位置不走,走法为0  
                else    mv[i][j]=mv[i][j-1]+mv[i-1][j];
            }
        }
        return mv[x][y];
    }
}
发表于 2019-09-14 11:29:52 回复(4)
张蔓鹭头像 张蔓鹭
js的同学不要忘了js最大能存16位数字，超过这个长度要用特殊的算法.....
js大整数相加： 

	
	

		function sumBigNumber(a, b) {
	


	

		var res = '',
	


	

		temp = 0;
	


	

		a = a.split('');
	


	

		b = b.split('');
	


	

		while (a.length || b.length || temp) {
	


	

		temp += ~~a.pop() + ~~b.pop();
	


	

		res = (temp % 10) + res;
	


	

		temp = temp > 9;
	


	

		}
	


	

		return res.replace(/^0+/, '');
	


	

		}

编辑于 2019-07-24 17:28:01 回复(0)
名字的响亮的头像 名字的响亮的
这个题目测试用例比较宽松，boss的位置不在(x,0)或者(0,y)这样的位置上。
测试用例
2 2  1
0 1
结果应该是 3
2 2  1
0 0（这个比较坑，假设Boss就坐在门口）
结果应该是 0

编辑于 2019-06-17 21:43:02 回复(6)
dragonlogin头像 dragonlogin 

/*
 * 对于此题的几点总结：
 * 1.牛客喜欢把大样例卡在最前面。这也就是之前，为什么样例通过了，却通过率为0的原因。
 * 2.此题为 障碍型坐标型计数型动态规划
 * */
#include <bits/stdc++.h>
using  namespace std;
const int N = 31;
typedef long long ll; // 重点，第一次用的int，答案溢出了
int m[N][N];
ll f[N][N];
int main() {
    int x,y,n;
    int i,j;
    while (cin >> x >> y >> n) {
        for (int k=0; k<n; ++k) {
            cin >> i >> j;
            m[i][j] = 1; // 障碍标记为 1
        }
        f[0][0] = 1;
        for (i=0; i<=x; ++i) {
            for (j=0; j<=y; ++j) {
                if (m[i][j] == 1) {
                    f[i][j] = 0; // 如果是障碍， 则不可能走到
                } else {
                    // 这样写法的好处是：不用对第一行，第一列单独处理
                    if (i-1>=0) {
                        f[i][j] += f[i-1][j];
                    }
                    if (j-1>=0) {
                        f[i][j] += f[i][j-1];
                    }
                }
            }
        }
        cout << f[x][y] << endl;
    }
    return 0;
}

编辑于 2019-10-17 11:33:35 回复(0)
Java
NyaNyaRu头像 NyaNyaRu
太坑了Long
发表于 2022-03-18 21:38:15 回复(0)
pein531头像 pein531
常规动态规划，其实左下角右上角这个描述没什么用，因为左下角坐标为(0,0)，仍然可以理解为左上角走到右下角。在状态转移的时候累加上一次位置的方案数（上一个位置不能是boss的位置）就行 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int x = Integer.parseInt(params[0]);
        int y = Integer.parseInt(params[1]);
        int n = Integer.parseInt(params[2]);
        long[][] dp = new long[x + 1][y + 1];
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            dp[Integer.parseInt(params[0])][Integer.parseInt(params[1])] = -1L;
        }
        for(int i = 0; i <= x; i++) dp[i][0] = 1L;
        for(int j = 0; j <= y; j++) dp[0][j] = 1L;
        for(int i = 1; i <= x; i++){
            for(int j = 1; j <= y; j++){
                if(dp[i][j] == -1) continue;       // 当前是老板的位置
                if(dp[i - 1][j] != -1) dp[i][j] += dp[i - 1][j];   // 从上面转移过来
                if(dp[i][j - 1] != -1) dp[i][j] += dp[i][j - 1];   // 从左边转移过来
            }
        }
        System.out.println(dp[x][y]);
    }
}

发表于 2021-09-07 14:47:55 回复(0)
国家一级陪跑运动员头像 国家一级陪跑运动员
用Go的实现，规避障碍的动态规划，状态转移方程为dp[i][j] = dp[i-1][j] + dp[i][j-1]，再把base状态补上就行 
package main

import (
	"fmt"
)

func main() {
	var (
        arr [][]int
        init bool
    )
	for {
		var x, y, n int
		t, _ := fmt.Scanln(&x, &y, &n)
		if !init && t == 3 {
			arr = make([][]int, x+1)
			for i := range arr {
				arr[i] = make([]int, y+1)
			}
            init = true
		} else if t == 2 && x < len(arr) && y < len(arr[0]) {
			arr[x][y] = -1
		} else {
			break
		}
	}

	// 初始化二维切片
	for i := range arr {
		arr[i][0] = 1
	}

	for j := range arr[0] {
		arr[0][j] = 1
	}


	for i := 1; i < len(arr); i++ {
		for j := 1; j < len(arr[0]); j++ {
			if arr[i][j] == -1 {
				arr[i][j] = 0
			} else {
				arr[i][j] = arr[i-1][j] + arr[i][j-1]
			}
		}
	}

	fmt.Println(arr[len(arr)-1][len(arr[0])-1])
}


发表于 2020-06-12 15:29:45 回复(1)
ac_q头像 ac_q 
也许这就是差距吧，别人的代码简介，而我的，，，

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

int main()
{
	int x = 0;
	int y = 0;
	int n = 0;
	cin >> x >> y >> n;
	vector<vector<long long>> vv(x + 1, vector<long long>(y + 1, 0));
	vector<vector<long long>> dp(x + 1, vector<long long>(y + 1, 0));
	for (int i = 0; i < n; i++)
	{
		int a = 0;
		int b = 0;
		cin >> a >> b;
		vv[x - a][b] = 1; //陷阱
	}
	for (int i = 0; i < vv[0].size(); i++)
	{
		if (vv[x][i] == 0)
		{
			dp[x][i] = 1;
		}
		else
		{
			//为1是陷阱
			break;
		}
	}
	for (int i = x; i >= 0; i--)
	{
		if (vv[i][0] == 0)
		{
			dp[i][0] = 1;
		}
		else
		{
			break;
		}
	}
	for (int i = x - 1; i >= 0; i--)
	{
		for (int j = 1; j <= y; j++)
		{
			if (vv[i][j] == 1)
			{
				dp[i][j] = 0;
				continue;
			}
			else
			{
				dp[i][j] = dp[i + 1][j] + dp[i][j - 1];
			}
		}
	}
	cout << dp[0][y] << endl;

}

发表于 2020-06-03 22:10:53 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 31;

int main(){
    int x,y,n;
    cin>>x>>y>>n;
    ll dp[N][N];
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        dp[a][b] = -1;
    }
    for(int i=0;i<=x;i++)
        dp[i][0] = 1;
    for(int i=0;i<=y;i++)
        dp[0][i] = 1;
    for(int i=1;i<=x;i++)
        for(int j=1;j<=y;j++){
            if(dp[i][j]==-1)
                continue;
            if(dp[i-1][j]!=-1)
                dp[i][j] += dp[i-1][j];
            if(dp[i][j-1]!=-1)
                dp[i][j] += dp[i][j-1];
        }
    cout<<dp[x][y]<<endl;
    return 0;
}

发表于 2019-12-09 08:57:56 回复(0)
C/C++
昔遥暮云头像 昔遥暮云 
//动态规划
#include <bits/stdc++.h>
using namespace std;
int main(){
    int x,y,n;
    cin>>x>>y>>n;
    vector<vector<long long>> dp(x+1,vector<long long>(y+1,1));
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        dp[a][b]=0;
    }
    for(int i=1;i<=x;i++)
        dp[i][0]= dp[i][0]!=0 ? dp[i-1][0]:0;
    for(int j=1;j<=y;j++)
        dp[0][j]= dp[0][j]!=0 ? dp[0][j-1]:0;
    for(int i=1;i<=x;i++)
        for(int j=1;j<=y;j++)
            if(dp[i][j]!=0)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
    cout<<dp[x][y];
    return 0;
}

发表于 2019-12-03 10:29:56 回复(0)
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,y,n,xi,yi;
    cin>>x>>y>>n;
    vector<vector<long long>>dp(x+1,vector<long long>(y+1,0));
    vector<vector<int>>num(x+1,vector<int>(y+1,0));
    for(int i=0;i<n;i++)
    {
        cin>>xi>>yi;
        num[xi][yi]=1;
    }
    for(int i=1;i<x+1;i++)
    {
        if(num[i][0]==0)
            dp[i][0]=1;
        else
            while(i<=x)
            {
                dp[i][0]=0;
                i++;
            }
    }
    for(int j=1;j<y+1;j++)
    {
        if(num[0][j]==0)
            dp[0][j]=1;
        else
            while(j<=y)
            {
                dp[0][j]=0;
                j++;
            }
    }
    for(int i=1;i<x+1;i++)
    {
        for(int j=1;j<y+1;j++)
        {
            if(num[i][j]==0)
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            else
                dp[i][j]=0;
        }
    }
    cout<<dp[x][y]<<endl;
    return 0;
}

发表于 2019-08-22 21:07:00 回复(0)
offer快到碗里来啊！头像 offer快到碗里来啊！ 
import java.util.Scanner;

/**
 * @Classname Shopee_01
 * @Description TODO
 * @Date 19-7-11 下午2:08
 * @Created by mao<tianmao818@qq.com>
 */
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);

        while(sc.hasNext()){
            int x=sc.nextInt();
            int y=sc.nextInt();
            long[][] path=new long[x+1][y+1];
            int n=sc.nextInt();
            for(int i=0;i<n;i++){
                int a=sc.nextInt();
                int b=sc.nextInt();
                path[a][b]=-1;
            }
            
            for(int i=0;i<=x;i++){
                path[i][0]=1;
            }
            for(int j=0;j<=y;j++){
                path[0][j]=1;
            }
            for(int i=1;i<=x;i++){
                for(int j=1;j<=y;j++){
                    if(path[i][j]==-1){
                        path[i][j]=0;
                    }else{
                        path[i][j]=path[i][j-1]+path[i-1][j];
                    }
                }
            }

            System.out.println(path[x][y]);
        }
    }
}

发表于 2019-07-11 15:04:08 回复(6)
Justina201902231405279头像 Justina201902231405279 
#include<iostream>
using namespace std;

int main() {
    int x, y, n;
    cin >> x >> y >> n;
    long long int dp[30 + 1][30 + 1] = {0};
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        dp[x][y] = -1;
    }
    for (int i = 0;i <= x;i ++) dp[i][0] = 1;
    for (int j = 0;j <= y;j ++) dp[0][j] = 1;
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            if (dp[i][j] == -1) continue;
            if (dp[i - 1][j] != -1) dp[i][j] += dp[i - 1][j];
            if (dp[i][j - 1] != -1) dp[i][j] += dp[i][j - 1];
        }
    }
    cout << dp[x][y] << endl;
    return 0;
}
发表于 2019-07-21 23:25:17 回复(7)
风度翩翩的单身狗很热情头像 风度翩翩的单身狗很热情 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        int x = sr.nextInt();
        int y = sr.nextInt();
        int n = sr.nextInt();
        int [][] location = new int[x + 1][y + 1];
        for (int i = 0; i < n; i++) {
            int x1 = sr.nextInt();
            int y1 = sr.nextInt();
            location[x1][y1] = 1;
        }
        System.out.println(solution(location, x, y));
    }

    private static long solution(int[][] location, int x, int y) {
        long[][] dp = new long[x+1][y+1];
        dp[0][0] = 1;
        for (int i = 1; i <= y; i++) {
            dp[0][i] = location[0][i] == 1 ? 0 : dp[0][i-1];
        }
        for (int i = 1; i <= x; i++) {
            dp[i][0] = location[i][0] == 1 ? 0 : dp[i-1][0];
        }
        for (int i = 1; i <= x; i++) {
            for (int j = 1; j <= y; j++) {
                dp[i][j] = location[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[x][y];
    }
}


发表于 2023-09-24 16:09:53 回复(0)
C++
牛客409434554号头像 牛客409434554号 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,y,n;
    cin>>x>>y>>n;
    long long a[y+1][x+1];
    memset(a,0,sizeof(a));
    for(int i=0;i<n;i++)
    {
        int a1,b1;cin>>a1>>b1;
        a[b1][a1]=-1;
    }
    for(int i=0;i<x+1;i++)    
        if(a[0][i]!=-1)    a[0][i]=1;
    for(int i=0;i<y+1;i++)    
        if(a[i][0]!=-1)    a[i][0]=1;
    for(int i=1;i<y+1;i++)
        for(int j=1;j<x+1;j++)
        {
            if(a[i][j]==-1)    continue;
            else
            {
                if(a[i-1][j]!=-1)
                    a[i][j]+=a[i-1][j];
                if(a[i][j-1]!=-1)
                    a[i][j]+=a[i][j-1];
            }
        }
      cout<<a[y][x]<<endl;
}
这个题没有BOSS在门口的情况，所以不用考虑0,0（谁家BOSS坐大门口，哈哈）
然后注意数组的范围，边界的包裹，简单的动态规划，BOSS 位置设置成-1就行了，遇到BOSS 跳过，方法数不加BOSS位的就行了，比如：如果BOSS 在某一个位置的左侧，那这个位置只能是从下面上来，那就跟下面的方法数一致，如果BOSS在某个位置下面，那只能从左侧过来，和左侧方法数一致。如果左和下都没BOSS ，那自然是两者相加。
发表于 2022-01-17 03:35:02 回复(0)
牛客340089816号头像 牛客340089816号 
import java.util.Scanner; public class Main { static int result = 0; static int x; static int y; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int x = scanner.nextInt(); int y = scanner.nextInt(); Main.x = x; Main.y = y; int boss_num = scanner.nextInt(); int[][] boss_pos = new int[x+1][y+1]; long[][] dp = new long[x+1][y+1]; for (int i = 0; i<boss_num; i++){ boss_pos[scanner.nextInt()][scanner.nextInt()] = 1;
        } count(x, y, dp, boss_pos); System.out.println(dp[x][y]);
    } private static void count(int x, int y, long[][] dp, int[][] boss_pos) {
       dp[0][0] = 0; //第0行  for (int j = 1; j<=y; j++){ if (boss_pos[0][j] == 1){
                dp[0][j] = 0; break;
            }else{
                dp[0][j] = 1;
            }
        } //第0列  for (int i = 1; i<=x; i++){ if (boss_pos[i][0] == 1){
                dp[i][0] = 0; break;
            }else{
                dp[i][0] = 1;
            }
        } for (int i =1 ; i <= x; i++){ for (int j = 1 ; j <= y; j++){ if (boss_pos[i][j] == 1){
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
    } private static void DFS(int x, int y, int[][] boss_pos) { if (x == Main.x && y == Main.y){ result++; return;
       } if (boss_pos[x][y] == 1){ return;
       } if( y+1 <= Main.y){ // 向上  DFS(x, y+1, boss_pos);
       } if( x+1 <= Main.x){ // 向右  DFS(x+1, y, boss_pos);
        }
    }

}
发表于 2021-07-31 12:36:31 回复(0)
ZeRo1.头像 ZeRo1.
//考虑了老板位置可能在第一行或第一列的情况，以及门口可能有老板的情况

#include <vector>
#include <iostream>

using namespace std;

int main() {
    int x = 0, y = 0, n = 0;
    cin >> x >> y >> n;
    vector<vector<int>> path(x+1, vector<int>(y+1, 0));
    vector<vector<long long>> dp(x+2, vector<long long>(y+2, 0));
    for (int i = 0; i < n; ++i) {
        int xi = 0, yi = 0;
        cin >> xi >> yi;
        path[xi][yi] = 1;
    }
    dp[0][1] = 1;
    if (path.empty() || path[0].empty() || path[0][0] == 1) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= x+1; ++i) {
        for (int j = 1; j <= y+1; ++j) {
            if (path[i-1][j-1] == 1) continue;
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    cout << dp[x+1][y+1] << endl;
    return 0;
}
发表于 2021-07-03 17:15:30 回复(0)
数据小随从头像 数据小随从 
        import java.util.*;

        import java.lang.*;

        public class Main {

            public static void main(String[] args){

                Scanner sc = new Scanner(System.in);

                int m = sc.nextInt();

                int n = sc.nextInt();

                int bosses = sc.nextInt();

                int[][] boss = new int[m + 1][n + 1];

                for (int i = 0; i bosses; i++){

                    int x = sc.nextInt();

                    int y = sc.nextInt();

                    boss[x][y] = -1;

                }

                long[][] dp = new long[m + 1][n + 1];

                for (int i = 0; i m; i++){

                    for (int j = 0; j n; j++){

                        if (boss[i][j] == -1){

                            continue;

                        } else if (i == 0 && j == 0){

                            dp[i][j] = 1L;

                        } else if (i == 0){

                            dp[i][j] = dp[i][j - 1];

                        } else if (j == 0){

                            dp[i][j] = dp[i - 1][j];

                        } else {

                            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

                        }

                    }

                }

                System.out.println(dp[m][n]);

            }

        }
发表于 2021-06-09 17:50:58 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 动态规划 深圳虾皮信息科技有限公司 2019 数学 Java工程师
来自：Shopee 2019...
上传者：小小
难度：
53条回答 19478浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Shopee的办公室（二）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号