Giải bài tập Hệ thống phòng thủ bằng C/C++

Giải bài tập Hệ thống phòng thủ bằng C/C++

Hãy tưởng tượng bạn đang tham gia một trò chơi có tên là " Hệ thống phòng thủ". Ở mỗi mức chơi (level) người chơi phải bảo vệ một vùng đất hình chữ nhật có dạng mạng lưới các ô vuông. Người chơi xây dựng các tháp phòng thủ tại một vài vị trí trên vùng đất đó. Một tháp phòng thủ sẽ bảo vệ toàn bộ vùng đất nằm trên dòng và cột mà tháp canh đó đặt. Không có hai tháp phòng thủ nào nằm trên cùng một dòng hay một cột.

Khi đặt tháp phòng thủ như vậy sẽ có những vùng đất không được bảo vệ. Hãy tính số ô vuông lớn nhất mà không được tháp canh bảo vệ.

Ở ví dụ dưới đây vùng đất lớn nhất mà không được tháp canh bảo vệ là 12 ô vuông.

he thong phong thu

[Input]

Dữ liệu được đọc vào từ file "DEFENSE.INP".

*Dòng đâu tiên chứa 3 số nguyên dương. w - chiều rộng của ma trận lưới các ô vuông. h - chiều cao của ma trận lưới các ô vuông và n là số lượng tháp phòng thủ.

* n dòng tiếp theo là vị trí của các tháp phòng thủ.

[Output]

Ghi số ố vuông lớn nhất không được bảo vệ ra file "DEFENSE.OUT".

[Input sample]

15 8 3
3 8
11 2

8 6

[Output sample]

12

[Giải thuật]

- Các tháp phòng thủ được đặt trên một ma trận mạng lưới và không có 2 tháp nào cùng nằm trên cùng một hàng hay một cột. Thực hiện phép chiếu vuông góc tới 2 trục tọa độ x và y, được tọa tọa độ của các tháp trên trục x và trục y.

- Sắp xếp tọa độ của các tháp phòng thủ theo chiều tăng dần của x và xét hiệu ci = Xi – Xi-đây là khoảng cách giữa hai tháp theo trục x.

- Sắp xếp tọa độ của các tháp phòng thủ theo chiều tăng dần của y và xét hiệu di = Yi – Yi-đây là khoảng cách giữa hai tháp theo trục y.

Vùng đất có kích thước w*h, ta có thể đặt thêm một tháp canh tại vị trí [w+1][h+1] để tính khoảng cách từ tháp cuối ( tận cùng bên phải) tới cuối vùng đất.

- Giả sử khu đất không được bảo vệ có kích thước a*b ô vuông, khi đó a <= ci max , b <= di max. Vậy vùng đất lớn nhất mà không được bảo vệ là ci max * di max là lời giải của bài toán.

Chương trình cài đặt:

#include<iostream>

#include <cstdio>

using namespace std;

#define WMAX 40002

#define HMAX 40002

int xAxis[WMAX],yAxis[HMAX];

int main(){

 freopen("DEFENSE.INP","r",stdin);

 freopen("DEFENSE.OUT","w",stdout);

 int w, h,n;

 cin>>w>>h>>n;

 int tempx,tempy;

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

  cin>>tempx>>tempy;

  xAxis[tempx] = 1;

  yAxis[tempy] = 1;

 }

 // đặt 1 tòa tháp vào góc trên bên phải.

 xAxis[w+1] = 1;

 yAxis[h+1] = 1;

 int maxX = 0;

 int tempMax = 0;

 for(int i=1;i<= w + 1;i++){

  if(xAxis[i]==0){

   tempMax++;

  }else{

   if(tempMax > maxX) maxX = tempMax;

   tempMax = 0;

  }

 }

 int maxY = 0;

 tempMax =0;

 for(int i=1;i <= h + 1;i++){

  if(yAxis[i]==0){

   tempMax++;

  }else{

   if(tempMax > maxY) maxY = tempMax;

   tempMax = 0;

  }

 }

 cout<<maxX*maxY;

 return 0;

}

 

Bạn thấy bài viết này như thế nào?: 
No votes yet
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
10 điểm Kindle Fire 2 cần có để đọ với Nexus 7

10 điểm Kindle Fire 2 cần có để đọ với Nexus 7

Phần cứng của Nexus 7 vượt hẳn Kindle Fire 2 dù cùng mức giá. Vì thế nhiều người tin rằng Kindle Fire thế hệ hai sẽ có bộ xử lí lõi tứ, màn hình xịn hơn, thiết kế đẹp mắt và nhiều "vũ khí" khác để đấu lại MTB của Google.

Review of the Samsung Galaxy S II

Review of the Samsung Galaxy S II

The Samsung Galaxy S II is a very stylish smart phone.  From the moment I held it in my hands; I fell in love with it. It totally looks amazing.

Google Street View “nhìn xuyên thấu” các tòa nhà

Google Street View “nhìn xuyên thấu” các tòa nhà

Google đã bắt đầu thử nghiệm tính năng mới, cho phép người dùng có thể… nhìn vào bên trong các căn nhà, đặc biệt là các nhà hàng và viện bảo tàng để có thể thấy được cả những gì đang có trong đó.