## itzmevacho

BAN USER- 2of 4 votes

AnswersAlex is standing on the top left cell (1,1) of a n*m table. The table has n rows and m columns. Initially, he is facing its right cell. He moves on the table in the following way:

- itzmevacho in United States

>He moves one step forward.

>He turns to his right

>While moving forward, if he would go out of the table or reach a visited cell, he turns to his right.

He moves in the table as much as he can. Can you find out the number of cells he visits before he stops?

For example, given a 9x9 grid, the following would be his moves. The number on each cell represents the step he would land on that particular cell.

1 2 55 54 51 50 47 46 45

4 3 56 53 52 49 48 43 44

5 6 57 58 79 78 77 42 41

8 7 60 59 80 75 76 39 40

9 10 61 62 81 74 73 38 37

12 11 64 63 68 69 72 35 36

13 14 65 66 67 70 71 34 33

16 15 20 21 24 25 28 29 32

17 18 19 22 23 26 27 30 31

Input:

The first line of the input contains two integer numbers n and m.

n and m are between 1 and 100.

Output:

Print an integer to the output being the answer of the test.

Sample input #00:

3 3

Sample output #00:

9

Sample input #01:

7 4

Sample output #01:

18| Report Duplicate | Flag | PURGE

Facebook Front-end Software Engineer - 1of 3 votes

AnswersWe have a rectangle with n rows and m columns filled with numbers from 1 to n*m.

- itzmevacho in United States

Cell (i,j) of the rectangle is important iff:

* i = 1 and j = 1 (or)

*there is an important cell (a,b) such that (a,b) is a neighbor of (i,j) and the number

on (i,j) is greater than number on cell (a,b) and all of (a,b)'s neighbors except for (

(i,j) itself

Two cells are considered to be neighbors if they share a common edge between them.

Unfortunately the number in some of the cells has been erased. We want to write a number to those cells such that the resultant rectangle has all the numbers between 1 to n*m and it contains as many important cells as possible. In case there are several ways to do that, we are interested with the rectangle which is lexicographically smallest.

A table is lexicographically smaller that the other if the string of its row-major view is lexicographically smaller than the other.

Input:

The first line of the input contains two integers n and m, Each of the next n lines contains m tokens. Each token is either an integer between 1 and n*m or '?'.

Output:

Print the maximum number of important cells that can be obtained in the first line of the output and print the rectangle in the next n lines.

Constraints:

1 <=n,m <=6

Sample input #00:

2 3

2 ? ?

? ? 3

Sample output #00:

3

2 1 4

5 6 3

Sample input #01:

6 6

? ? ? ? ? ?

? ? ? ? ? ?

? ? ? ? ? ?

? ? ? ? ? ?

? ? ? ? ? ?

? ? ? ? ? ?

Sample output #02:

24

1 2 3 13 14 15

4 6 8 10 11 16

5 7 9 12 19 17

28 26 24 22 20 18

29 27 25 23 21 36

30 31 32 33 34 35| Report Duplicate | Flag | PURGE

Facebook Front-end Software Engineer

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.