7.31 阿里笔试
1.
有n只体重各不相同的牛，可能的颜色有m种。放一些牛，问有多少种可能，1e9+7取模。
二项式定理+快速幂
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
ll n, m;
ll powmod(ll x,ll n ,ll mod)
{
ll res=1;
while(n>0)
{
if(n&1LL) res=res*x%mod ;
x=x*x%mod;
n>>=1;
}
return res ;
}
int main()
{
ll mod = 1000000007;
scanf("%lld %lld", &n, &m);
m++;
printf("%lld\n", powmod(m, n, mod));
return 0;
} 2.
n*m的矩阵，由字符'S'和'C'组成，S表示海洋，C表示陆地，从陆地到陆地消耗体力3，从海洋到海洋消耗体力2，从陆地到海洋或者从海洋到陆地都需要消耗体力5。
输入q（q<10）个查询，每个查询bx，by，ex，ey分别表示起点坐标和终点坐标，输出每组中消耗的最小体力。
bfs搜索
#include <bits/stdc++.h>
using namespace std;
int n, m, q;
char mp[505][505];
int vis[505][505];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int bx,by,ex,ey;
struct node{
int x,y;
node(int xx,int yy):x(xx),y(yy){}
};
int main()
{
scanf("%d %d %d", &n, &m, &q);
for(int i = 0 ; i < n ; i++)
scanf("%s", mp[i]);
while(q--){
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < m ; j++)
vis[i][j] = 10000000;
scanf("%d %d %d %d", &bx, &by, &ex, &ey);
bx--;by--;ex--;ey--;
vis[bx][by] = 0;
queue<node> que;
que.push(node(bx, by));
while(!que.empty()){
node t = que.front();
que.pop();
for(int i = 0 ; i < 4 ; i++){
int x = t.x + dx[i];
int y = t.y + dy[i];
if(x<0 || x>=n || y<0 || y>=m) continue;
int w = 5;
if(mp[x][y]==mp[t.x][t.y]){
if(mp[x][y]=='C')
w = 3;
else w = 2;
}
if(vis[x][y] <= vis[t.x][t.y]+w)
continue;
vis[x][y] = vis[t.x][t.y] + w;
que.push(node(x,y));
}
}
printf("%d\n", vis[ex][ey]);
}
return 0;
}
/*
4 4 2
CCCS
SSSS
CSCS
SSCC
1 1 3 4
3 1 1 3
*/ 
