oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

catneighbours Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

catneighbours.html

Problem Description

A bunch of N cats have taken over a H by W units wide space. They have divided it into blocks of 1 by 1 unit and each block is 'owned' by 1 cat. However, a cat can own more than one block and the blocks a cat owned need not be adjacent.

Cats hate socialising with their neighbours but are still curious about how many neighbours they have.

If two cats own blocks which share an edge (not corner), they are known to be neighbours with each other. In other words, if two blocks are adjacent in 4-directional movement, the owners of these two blocks will be neighbours with each other.

Cats are labelled from 0 to N-1 and you will be provided with a H by W map denoting which cat owns which block.

For each cat, output the number of neighbours it has! It is possible that a cat happen to not own any blocks. In that case, it will have 0 neighbours.

Limits

Subtask 1 (23%): 1 ≤ H, W ≤ 10, 1 ≤ N ≤ 100.

Subtask 2 (28%): 1 ≤ H, W ≤ 100, 1 ≤ N ≤ 1000

Subtask 3 (49%): 1 ≤ H, W ≤ 1000, 1 ≤ N ≤ 1000000

Subtask 4 (0%): Sample Testcases.

Input

The first line of input will contain three integers, H, W followed by N.

There will be H lines containing W integers each. Each integer will be between 0 and N-1 and they represent who is the owner of that block.

Output

The output should contain N integers, the ith integer should be the number of neighbours a cat has.

Sample Testcase 1

Input

3 3 5
1 3 4
2 0 1
3 1 2

Output

3
4
3
4
2

Explanation

Cat 0 has 3 neighbours: 1, 2 and 3.

Cat 1 has 4 neighbours: 0, 2, 3 and 4. They are adjacent to either one of the 3 Cat 1's blocks.

Cat 2 has 3 neighbours: 0, 1 and 3.

Cat 3 has 4 neighbours: 0, 1, 2 and 4.

Cat 4 only has 2 neighbours: 1 and 3.

Sample Testcase 2

Input

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

Output

1
1
0

Explanation

Cat 0 and Cat 1 are neighbours.

Cat 2 does not have any block and thus have 0 neighbours.

Sample Testcase 3

Input

1 5 5
0 1 2 3 4

Output

1
2
2
2
1

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
123222s256MBMinimum
228352s256MBMinimum
349562s256MBMinimum
4032s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o catneighbours -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.