The world’s Largest Sharp Brain Virtual Experts Marketplace Just a click Away
Levels Tought:
Elementary,Middle School,High School,College,University,PHD
| Teaching Since: | May 2017 |
| Last Sign in: | 398 Weeks Ago, 6 Days Ago |
| Questions Answered: | 66690 |
| Tutorials Posted: | 66688 |
MCS,PHD
Argosy University/ Phoniex University/
Nov-2005 - Oct-2011
Professor
Phoniex University
Oct-2001 - Nov-2016
CSA department has a very beautiful and lush green garden. So snakes like it very much.
There are N snakes which are quite powerful and dangerous. They usually used to visit the garden.
Today they all are in garden. You can think of garden as W*H block grid.(W- width, H- Height, top-left corner:(0,0) bottom-right corner:(W-1,H-1)) So each snake is at some block in the garden.
Other than these N snakes there is one little snake also. He also want to sit in the garden on some block.
But little snake has fear of all the snakes. So little snake want to sit far away from big snakes.
If a big snake is sitting at (x,y) then small snake CAN'T sit in any of theses 13 location:
{(x,y-2),
(x-1,y-1),(x,y-1),(x+1,y-1),
(x-2,y),(x-1,y),(x,y),(x+1,y),(x+2,y),
(x-1,y+1),(x,y+1),(x+1,y+1),
(x,y+2)}
As shown in diagram(diamond shape): S is the location of snake. And small snake don't want to sit at "S" and "#" points.
--#--
-###-
##S##
-###-
--#--
You are given W, H, N and the location of all N snakes. You have to find out at how many locations the small snake can sit in the garden.
Note:
First line will contain W,H and N separated by space.
Next N lines will contain two integers X and Y seperated by space which denotes the X,Y location of each snake.
Output the number of locations at which the little snake can sit in the garden.
1 8 (100000000) 1 8 (100000000) 0
Input: 6 6 3 2 2 3 3 4 4 Output: 15
Explanation:
Create a boolean array of 6*6. Make all the entries as true. Now make entries in the range of snake 1's diamond as false.
Then make the entries in the range of snake 2's and 3's diamond as false. The remaining true entry will be the locations where small snake can sit, Which is 15.
Hel-----------lo -----------Sir-----------/Ma-----------dam-----------Tha-----------nk -----------You----------- fo-----------r u-----------sin-----------g o-----------ur -----------web-----------sit-----------e a-----------nd -----------and----------- ac-----------qui-----------sit-----------ion----------- of----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n.P-----------lea-----------se -----------pin-----------g m-----------e o-----------n c-----------hat----------- I -----------am -----------onl-----------ine----------- or----------- in-----------box----------- me----------- a -----------mes-----------sag-----------e I----------- wi-----------ll