首页 > ACM题库 > HDU-杭电 > HDU 3675-Flight Control[解题报告]HOJ
2014
11-30

HDU 3675-Flight Control[解题报告]HOJ

Flight Control

问题描述 :

You’re the key programmer employed by a flight control center, and you’ve just been assigned a task which is to monitor the activity of aircrafts in a particular area.

Since some of the aircrafts in that area are so far away from the control that the sensors can’t get a lock on them, it is impossible to determine the actual number of aircrafts in that area; however, the scanning of the flight control’s sensor arrays has shown the amount of energy sensed in each grid of that area, and by analyzing that data, you will be able to get a general view of that area.

You have decided to first in order to write a program to simplify the calculation of the minimum number of aircrafts. you need to follow the following rules:

1. A grid from which the sensor arrays get no reading indicates a grid without any aircraft;
2. A grid with a positive value indicates a trace of an aircraft, and in that grid, a) An aircraft may be present, or b) It is the trace of exactly one aircraft traveling either horizontal or vertical (notice the aircraft can’t change the flying direction halfway);
3. If a series of adjacent grids on a row or a column are the trace of one aircraft, then the amount of energy in them (from top to bottom or from left to right) must be either strictly increasing or strictly decreasing.

输入:

There are multiple test cases in the input file. Each test case starts with two integers, N and M (1<=N<=50, 1<=M<=9) , the length and width of the area that the you’re monitoring. Each of the following N lines consists of M integers, the j -th integer on the i -th line representing the amount of heat sensed by the flight control’s sensor array. It is guaranteed that every integer in the input will fit into a 32-bit signed integer.

There is a blank line after each test case. A single line with N = 0 and M = 0 indicates the end of input file.

输出:

There are multiple test cases in the input file. Each test case starts with two integers, N and M (1<=N<=50, 1<=M<=9) , the length and width of the area that the you’re monitoring. Each of the following N lines consists of M integers, the j -th integer on the i -th line representing the amount of heat sensed by the flight control’s sensor array. It is guaranteed that every integer in the input will fit into a 32-bit signed integer.

There is a blank line after each test case. A single line with N = 0 and M = 0 indicates the end of input file.

样例输入:

3 3 
1 2 3
4 5 6
7 8 9

0 0

样例输出:

Case 1: 3

#include <stdio.h>
#include <string.h>
const int Mod=9973;

int cnt[2],box[2][Mod],now,pre;

struct edge{
 int to,next,num;
} e[2][120000];

void add(int u,int num)
{
 int idx=u%Mod;

 for(int p=box[pre][idx];p!=-1;p=e[pre][p].next)
 if (e[pre][p].to==u)
 {
 if (e[pre][p].num>num) e[pre][p].num=num;
 return ;
 }
 e[pre][cnt[pre]].to=u;e[pre][cnt[pre]].num=num;
 e[pre][cnt[pre]].next=box[pre][idx];box[pre][idx]=cnt[pre]++;
}

int a[100][20];
int b[20];
int base[20];

bool ok1(int i,int j)
{
 return (a[i][j]>a[i][j-1]&&a[i][j-1]>a[i][j-2])||
 (a[i][j]<a[i][j-1]&&a[i][j-1]<a[i][j-2]);
}

bool ok2(int i,int j)
{
 return (a[i][j]>a[i-1][j]&&a[i-1][j]>a[i-2][j])||
 (a[i][j]<a[i-1][j]&&a[i-1][j]<a[i-2][j]);
}

int main()
{
 int n,m;
 int T=0;

 base[0]=1;
 for(int i=1;i<=10;i++) base[i]=base[i-1]<<2;
 while(scanf("%d %d",&n,&m)==2)
 {
 if (n==0&&m==0) break;

 memset(box[0],-1,sizeof(box[0]));
 cnt[0]=0;
 now=1;pre=0;
 add(0,0);
 now=0;pre=1;
 for(int i=0;i<n;i++)
 for(int j=0;j<m;j++)
 {
 scanf("%d",&a[i][j]);
 memset(box[pre],-1,sizeof(box[pre]));
 cnt[pre]=0;
 //printf("cnt=%d ",cnt[now]);
 for(int p=0;p<cnt[now];p++)
 {
 int v=e[now][p].to;
 int tmp=v;
 int num=e[now][p].num;
 int k=0;
 while(v)
 {
 b[k++]=v&3;
 v>>=2;
 }
 while(k<=m) b[k++]=0;
 tmp-=b[j+1]*base[j+1]+b[0];
 if (i==0) b[j+1]=0;
 if (j==0) b[0]=0;
 if (a[i][j]<=0)
 {
 add(tmp,num);
 continue;
 }
 if (b[0]==0) add(tmp+1,num+1); else
 if (b[0]==1&&a[i][j]!=a[i][j-1]) add(tmp+2,num) ; else
 if (ok1(i,j)) add(tmp+2,num); else
 add(tmp+1,num+1);

 if (b[j+1]==0) add(tmp+base[j+1],num+1); else
 if (b[j+1]==1&&a[i][j]!=a[i-1][j]) add(tmp+2*base[j+1],num); else
 if (ok2(i,j)) add(tmp+2*base[j+1],num); else
 add(tmp+base[j+1],num+1);
 }
 // puts("OK");
 now^=1;pre^=1;
 }
 int ans=n*m;
 for(int i=0;i<cnt[now];i++)
 if (ans>e[now][i].num) ans=e[now][i].num;
 printf("Case %d: %d\n",++T,ans);
 }
 return 0;
}

  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。