阿里笔试4.8

 //第二题：地图问题，在n*n地图上，从左上角出发，每次沿着上下左右任意方向移动距离小于k，移动位置需要价值高于当前位置价值。求路上的最大累计价值
#include <iostream>
#include <fstream>
#include <queue>
#include <tuple>
using namespace std;
//用广度优先搜索，由于下次节点值比本次大，所以无需用mark矩阵记录走过位置。
//状态节点包括(x,y,fees)  前两个是坐标，第三个是累计花销，并在入队列处滚动刷新最大花销值

int main(){
	ifstream fin("input.txt");
	int A[100][100];
	int n,k;
	
	fin>>n>>k;
	
	//读入矩阵 
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			fin>>A[i][j];
		}
	}
	int maxfees=0;
	int dx[4]={1,0,-1,0};
	int dy[4]={0,1,0,-1};
	
	queue<tuple<int,int,int>> q;
	q.push(make_tuple(0,0,A[0][0]));
	
	while(!q.empty()){
		auto item=q.front();q.pop();
		int x=get<0>(item);
		int y=get<1>(item);
		int fees=get<2>(item);
		maxfees=max(maxfees,fees);
			
		for(int d=0;d<4;d++){
			int nx=x;int ny=y;
			for(int tk=k;tk>0;tk--){
				nx=nx+dx[d];ny=ny+dy[d];
				if(0<=nx && nx<n && 0<ny && ny<n &&A[nx][ny]>A[x][y]){
					int nfees=fees+A[nx][ny];
					q.push(make_tuple(nx,ny,nfees));				
				}
			}
		}
		
	}	
	cout<<maxfees;
} 

#include <iostream>
using namespace std;
int main(){
	int n,m,a,b;
	cin>>n>>m>>a>>b;
	if(b>m){
		cout<< (n >=a? n:0);
	}else{
		int res=n*b/a;
		cout<< (res > m? m:res);
	}
}