The Mine FieldProblem code: M1 |
All submissions for this problem are available.
It's 2012. The times of peace are over. The Trojan Kingdom has just declared war on Byteland! As part of a massive defense plan against the Trojans, the Bytelandian Ministry of Defense (BMoD) wants to lay mines on a field near the borderline of the country.
The field has the form of a MxN rectangular grid divided into MxN unit-square cells. It is only possible to plant mines on some cells, and the number of mines on a cell cannot exceed one.
The objective is obviously to lay as many mines as possible. However, the BMoD does not want any two adjacent cells to both have mines, because such a situation would be dangerous: one mine being triggered could lead to a chain of explosions! Two cells are adjacent if they share a common edge.
Johnny, the most renowned computer scientist in Byteland, needs to compute the maximum number of mines that could be planted on the field, and the number of different ways in which these mines could be planted.
Hurry up and help Johnny save his beloved country!
Input
The first line contains T (about 15), the number of test cases. Then T test cases follow. Each test case has the following form.
The first line contains two numbers M and N representing the size of the field (1 <= M, N <= 20).
Each line in the next M lines contains N characters. Each character is either '.' or '*' representing the status of a cell in the field. A character '.' represents an empty cell (i.e. it is possible to lay a mine on that cell), while a character '*' represents a blocked cell (i.e. there are obstacles on that cell which prevent mines from being laid on it).
Input for successive test case is separated by a blank line.
Output
For each test case, print two numbers on a line. The first number is the maximum number of mines that could be planted on the field. The second number is the number of ways to plant the maximum number of mines on the field, modulo 151109.
Example
Input: 2 2 3 ... .*. 3 3 ... .*. ... Output: 3 1 4 2
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
bound on m & n are missing?
bound on m & n are missing?
Well, they're not missing;
Well, they're not missing; they just still haven't fixed the recurring problem of inequality signs not showing up. 1 M,N 20 means 1 <= M,N <= 20.
Fixed.
Fixed.
if say all the cells are
if say all the cells are bloked i.e. you can not place any mines ,
what will be the expected output
max mine :- 0
number of ways :- 0
please reply
Hi I am getting Runtime error
Hi
I am getting Runtime error (NZEC).
Language: Java
Any idea?
Why do you think you would be
Why do you think you would be given hints? You won't.
@xyz I don't think that's
@xyz I don't think that's right but since this is a competition I won't say any more.
@paras See the FAQ. It probably means that your program is throwing an exception somewhere. Unless the judge is broke, you won't get any more information than that.
Brian my case is an
Brian my case is an absolutely corner case,
this should be specified in problem statement .
it is like base case of an recursion, ( think f(n) = f(n - 1) + f(n -2) , would you be able to calculate if you have not been provided with f(0) and f(1))
please specify what is the expected behavior when you can not able to inset a single mine.
thanks
@XYZ: your question teeters
@XYZ: your question teeters on the line between hints and problem statement clarification. I'm inclined not to answer your question because it's not an ambiguous case. Read the problem statement carefully and hopefully the answer will come.
can any one tell me the cases
can any one tell me the cases of 2nd answer 4mines and 2 ways one way is (0,0) ,(2,0),(0,2)and(2,2)if matrix is a[3][3] if i understand wrong can any one elaborate a little
@satyendra other is (0,1)
@satyendra other is (0,1) (1,0) (1,2) (2,1)
Looks like Stephen cut the
Looks like Stephen cut the knot... nice job!
@everybody pls tell me is
@everybody
pls tell me is block 00 and 11 are adjacent...
pls help...
in 20*20 grid there is max
in 20*20 grid there is max mine is 200..than why is mode 151109
is it compulsory that we have
is it compulsory that we have to use . & * ...y cant we use any alphabets or numbers
lol this is funny .. i am
lol this is funny .. i am getting an Runtime error (OTHER) despite checking many times? Would it be too much to ask for error messages or the admin thinks ill print the test cases to stderr ? lol
m newbie hereits my first
m newbie here
its my first time
can u please tell me how to take input
whether as .txt file or somhw else???
anant mittal // by Standard
anant mittal // by Standard Input/Output
Anyway It seems like a
Anyway It seems like a typical problem tgat can be solved memoization, what I should do is to determine how to represent the status. I have an rough idea.. but I will think more because there should be a better way to do that.
Please don't discuss
Please don't discuss approaches to the problem until the contest is over.
Oops. I thought it was over.
Oops. I thought it was over. Sorry.
@anant Please don't post the
@anant Please don't post the same thing all over the place (although it's understandable that you would want a quick response with the competition about to end). See the FAQ.
@Ajay The maximum number of
@Ajay The maximum number of mines is, at most, 200, but the number of ways of placing the maximum number of mines might be bigger (I think...I haven't tried this sort of problem before).
@Bhavesh Yes, it is compulsory to use "." and "*", because the problem statement said so.
How long to view solution ?
How long to view solution ?
can anyone provide the
can anyone provide the algorithm for this problem??
Approaches have been
Approaches have been discussed in the forum.