营救行动
题目描述
一艘载有货物价值w的货船在海中搁浅了，它向周围船只发出SOS求救信号。距离最近的勇气号收到了SOS信号决定前往救援。随后，货船发来海图信息，这张图将海洋部分分化成n*n个比较小的单位，其中用1标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。勇气号每移动一格需要花费1单位时间，而同时货船上的货物每1单位时间损失1单位价值。当勇气号成功救援后，船上货物价值还剩多少？如果货船上货物价值已经损失完还没有得到救援，货船沉没，救援失败，输出-1.
输入输出格式
输入格式
第一行两个整数，n和w 接下来n行，每行n个字符，是一个n*n的0、1矩阵，表示海洋地图 最后一行为四个小于n的整数，分别表示勇气号和货船的位置
输出格式
1行，货船剩余价值
输入输出样例
输入样例#1:复 制
3 10 001 101 100 1 1 3 3
输出样例#1:复 制
6
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无
说明
N<=1000，保证存在从勇气号到货船的通路
错误代码 10分
#include<bits/stdc++.h>
using namespace std;
struct pos{int x,y;};
int ocean[1005][1005],path[1005][1005],n,start_x,start_y,end_x,end_y,ans,val;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int main(){
char ch;
cin>>n>>val;
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++){
cin>>ch;
ocean[x][y]=ch-'0';
}
}
cin>>start_x>>start_y>>end_x>>end_y;
ocean[start_x][start_y]=1;
pos p;
p.x=start_x;p.y=start_y;
queue<pos> qu;
qu.push(p);
while(!qu.empty()){
p=qu.front();qu.pop();
if (p.x==end_x&&p.y==end_y) break;
for (int i=0;i<4;i++){
int xx=p.x+dx[i];
int yy=p.y+dy[i];
if (!ocean[xx][yy]&&xx>=1&&xx<=n&&yy>=1&&yy<=n){
ocean[xx][yy] = 1;
path[xx][yy]=path[p.x][p.y]+1;
p.x=xx;p.y=yy;
qu.push(p);
}
}
}
val-=path[end_x][end_y];
if(val<0) cout<<-1;
else cout<<val;
return 0;
}
—————————————————————————————————————————————
计算面积
题目描述
编程计算由号围成的下列图形的面积。面积计算方法是统计号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示，在10x10的二维数组中，有*围住了15个点，因此面积为15。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 * * * 0 0 0 0 0 0 0 * 0 0 * 0 0 0 0 0 0 0 * 0 0 * 0 0 0 * 0 0 0 * 0 * 0 0 * 0 * 0 * 0 0 * 0 0 * 0 0 * * 0 * * 0 0 0 * 0 0 0 0 * 0 0 0 0 0 * * * * * 0 0 0 0 0 0 0 0 0 0 0 0
输入输出格式
输入格式
第一行两个整数，n，m表示图形的大小 第2行到n+1行，每行m个整数0或1，1表示*
输出格式
一行，一个整数，计算的面积
输入输出样例
输入样例#1:复 制
10 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
输出样例#1:复 制
15
输入样例#2:复 制
无
输出样例#2:复 制
无
输入样例#3:复 制
无
输出样例#3:复 制
无
说明
1<=n, m <= 20
错误代码 60分
#include<stdio.h>
#define N 101
int nex[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int vis[15][15];
struct node{
int x;
int y;
}q[N*100];
void bfs(int x,int y){
int head=1,tail=1;
q[tail].x=x;
q[tail].y=y;
tail++;
vis[x][y]=1;
while(head<tail){
int a=q[head].x;
int b=q[head].y;
for(int i=0;i<4;i++){
int nx=a+nex[i][0];
int ny=b+nex[i][1];
if(nx>=0&&nx<10&&ny>=0&&ny<10&&vis[nx][ny]==0){
vis[nx][ny]=1;
q[tail].x=nx;
q[tail].y=ny;
tail++;
}
}
head++;
}
}
int main(){
int i,j;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
scanf("%d",&vis[i][j]);
}
}
for(j=0;j<=9;j++){
if(vis[0][j]==0) bfs(0,j);
}
for(j=0;j<=9;j++){
if(vis[9][j]==0) bfs(9,j);
}
for(i=0;i<=9;i++){
if(vis[0][i]==0) bfs(0,i);
}
for(i=0;i<=9;i++){
if(vis[9][i]==0) bfs(9,i);
}
int sum=0;
for(i=0;i<10;i++){
for(j=0;j<10;j++){
if(vis[i][j]==0){
sum++;
}
}
}
printf("%d",sum);
return 0;
}