201409-4 最优配餐
bfs的应用,vis[][]标记是否访问,val[][]标记每一个点的值,为-1表示障碍,不为零表示用户点。
吐槽:这个外卖员不够机智啊,都不能一次性送多家
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n;
long long sum=0;
typedef struct {
int x,y;
int num;//走到这点的路程
}node;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool vis[N][N];
int val[N][N];
queue <node> q;
void bfs(){
while(!q.empty()){
node temp=q.front();
q.pop();
int cx,cy,cn,nx,ny,nn;
cx=temp.x;
cy=temp.y;
cn=temp.num;
sum+=val[cx][cy]*cn;
// if(cn) cout<<cx<<cy<<cn<<endl;
for(int i=0;i<4;i++){
nx=cx+dir[i][0];
ny=cy+dir[i][1];
nn=cn+1;
if(nx>n||ny>n||nx<1||ny<1||val[nx][ny]==-1) continue;
if(!vis[nx][ny]){
vis[nx][ny]=1;
temp.x=nx;
temp.y=ny;
temp.num=nn;
q.push(temp);
}
}
}
}
int main(){
int m,k,d;
cin>>n>>m>>k>>d;
int x,y,num;
memset(val,0,sizeof(val));
node temp;
for(int i=0;i<m;i++){
cin>>x>>y;
vis[x][y]=1;
temp.x=x;
temp.y=y;
temp.num=0;
q.push(temp);
}
for(int i=0;i<k;i++){
cin>>x>>y>>num;
val[x][y]+=num;
}
for(int i=0;i<d;i++){
cin>>x>>y;
val[x][y]=-1;
}
bfs();
cout<<sum<<endl;
// system("pause");
return 0;
}
//
201412-1
int main(){
cin>>n;
int num;
memset(index,0,sizeof(index));
for(int i=0;i<n;i++){
cin>>num;
index[num]++;
cout<<index[num]<<' ';
}
return 0;
}
201412-2
找规律,伤脑筋,容易出错
发现在CCF上测试得注意变量初始化,自己的编译器能正确输出,CCF测试却不能。
int val[505][505],n;
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>val[i][j];
}
}
int x=0,y=0;
for(int i=0;i<n;i++){
if(i%2==1){//偶数
for(int j=0;j<i;j++){
cout<<val[x++][y--]<<' ';
}
cout<<val[x++][y]<<' ';
}else{
for(int j=0;j<i;j++){
cout<<val[x--][y++]<<' ';
}
cout<<val[x][y++]<<' ';
}
}
if(n%2==1){
y--;
x++;
}else{
x--;
y++;
}
for(int i=n-2;i>0;i--){
if(i%2==1){
for(int j=0;j<i;j++)
cout<<val[x++][y--]<<' ';
cout<<val[x][y++]<<' ';
}else{
for(int j=0;j<i;j++){
cout<<val[x--][y++]<<' ';
}
cout<<val[x++][y]<<' ';
}
}
if(n!=1) cout<<val[n-1][n-1]<<endl;
return 0;
}