题目描述

小明在玩切水果游戏，已知屏幕上有若干水果，只允许用直线切水果，一次只允许划出一条直线，直线上的水果都会被消除掉；请求出小明最少要切多少次才能把屏幕上的水果都切掉。已知屏幕由40*50的小方格组成，经过每个方格划出的直线最多只有4条，如下图所示经过红色方格(标注为8)能划出直线最多为4条，其中相同数字的方格属于同一直线(0为空)；屏幕左上角坐标为(0,0)，右下角坐标为(39,49)。

|4|0|0|1|0|0|3|

|0|4|0|1|0|3|0|

|0|0|4|1|3|0|0|

|2|2|2|8|2|2|2|

|0|0|3|1|4|0|0|

|0|3|0|1|0|4|0|

|3|0|0|1|0|0|4|

输入描述

第一行输入整数N(0

输出描述

程序输出一个整数并换行，表示小明需要切水果的最少次数。

示例1

输入

2

3 4

2 2

输出

2

1.思考

本来是放弃第二题先做第三题的，结果发现第三题更难，只好硬着头皮写了……

先用coor记录下所有水果的位置坐标；

再用一个map表示每个位置的水果在横切、竖切、左上至右下切、右上至左下切四种方式下能够切到的其他的水果的id，这里的id直接就用输入先后顺序作为id；

然后用一个count记录每个位置的水果在一刀下最多能够切掉多少的水果；

接着每次都选择能够切掉最多水果的那个位置下的那一刀，并将已经切掉的水果从coor记录中删除；

之后依照新的coor记录重新建立map和count，重复上述过程，直至所有水果都消除。

因为没有线上提交，所以不太清楚这个方案是否能通过所有的测试集。我主要困惑的是，每次选择能切掉最多水果的那一刀，是否能够保证最后用的次数是最少的，这一点还没有想通，所以有可能思路是错误的，代码也写的不对……

2.实现

#include

#include

#include

using namespace std;

vector>> map;

void Hori(int index, vector> coor)

{

vector co = coor[index];

int len = coor.size();

for (int i = 0; i < len; i++){

if (i != index){

auto node = coor[i];

if (node[1] == co[1]){//same y label -

map[index][0].push_back(i);

}

}

}

}

void Vert(int index, vector> coor)

{

vector co = coor[index];

int len = coor.size();

for (int i = 0; i < len; i++){

if (i != index){

auto node = coor[i];

if (node[0] == co[0]){//same x label |

map[index][1].push_back(i);

}

}

}

}

void Left(int index, vector> coor)

{

vector co = coor[index];

int len = coor.size();

for (int i = 0; i < len; i++){

if (i != index){

auto node = coor[i];

if (node[0]-node[1]==co[0]-co[1]){//From top left to bottom right \

map[index][2].push_back(i);

}

}

}

}

void Right(int index, vector> coor)

{

vector co = coor[index];

int len = coor.size();

for (int i = 0; i < len; i++){

if (i != index){

auto node = coor[i];

if (node[0] + node[1] == co[0] + co[1]){//From top right to bottom left /

map[index][3].push_back(i);

}

}

}

}

//Calculate the max number of fruits when erase fruit i.

void CalMaxCount(vector& count)

{

int n = map.size();

int maxc = 0;

for (int i = 0; i < n; i++){

auto m = map[i];

maxc = 0;

for (int j = 0; j < 4; j++){

int lm = m[j].size();

maxc = maxc>lm?maxc:lm;

}

count[i] = maxc;

}

}

vector ConstMap(int n, vector>& coor)

{

map.clear();

//initial map

vector a;

vector> b;

for (int i = 0; i < 4; i++){

b.push_back(a);

}

for (int i = 0; i < n; i++){

map.push_back(b);

}

int lc = coor.size();

vector count(n);

for (int i = 0; i < lc; i++){

Hori(i, coor);

Vert(i, coor);

Left(i, coor);

Right(i, coor);

}

CalMaxCount(count);

return count;

}

bool cmp(int a, int b)

{

return a > b;

}

void CoorClear(int index, vector>& coor)

{

int len = coor.size(), pos = 0, maxc = 0;

auto m = map[index];

for (int j = 1; j < 4; j++){

if ( m[j].size() > maxc ){

maxc = m[j].size();

pos = j;

}

}

vector node = map[index][pos];

sort(node.begin(), node.end(), cmp);

for (int i = 0; i < maxc; i++){

coor.erase(coor.begin()+node[i]);

}

coor.erase(coor.begin() + index);

}

int main(){

int n;

while (cin>>n){

int x, y;

vector> coor;

vector count(n);

//input coordinate

for (int i = 0; i < n; i++){

cin >> x >> y;

coor.push_back(vector {x, y});

}

int res = 0, pos;

while(coor.size()){

//Construct Map

count = ConstMap(n, coor);

//Erase the line with most fruits.

pos = max_element(count.begin(), count.end()) - count.begin();

CoorClear(pos, coor);

res++;

}

cout << res<

}

return 0;

}