2016年2月25日 星期四

[HOJ 209]買醬油III 之 污漬問題 (題目備份)

HOJ生病惹QQ,因此在此悼念昔日光彩
題目備份,請參考~
題解在這裡
敬告:目前HOJ主機也許進入瀕死狀態了,常常無預警跳電。請看到這則公告的人能注意備份自己的資料,感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 
Submit  Ranklist

Problem : 209 - 買醬油III 之 污漬問題

Problem Statistics
Solved Member: 23  Submission: 215  User Tried: 27
Problem:
梓喵又回來買醬油了!!
自從上一次,梓喵去買醬油之後,你已經在路上被她撞到而得到幸福了。(如果你已經AC過這題的話...)

梓喵買了很多種醬油瓶,每一種醬油瓶可以用一個3x3的方塊表示。

方塊中的1代表污漬,0代表乾淨。

每一種醬油瓶,梓喵都買了無限多個,她想要挑出若干個醬油瓶,串成一個M瓶醬油瓶的橫向序列。

規定只有一個,排成的醬油瓶序列當中,不能有任何污漬上下左右相鄰。

梓喵現在想要問你,她有幾種相異擺法。

Input:
第一行有兩個數字N和M,其中用一個空格隔開,分別代表醬油瓶種類數量以及醬油瓶序列目標長度。(1 ≤ N ≤ 10, 1 ≤ M ≤ 10000000)
接下來有3xN行,每一行有3個字元,每3行代表一個醬油瓶,其中1代表污漬,0代表乾淨。

題目中所給的醬油瓶種類都是獨立的,也就是說,若有兩種醬油瓶污漬排列一模一樣,只要分開定義,就視為不同種。並且,任何醬油瓶都不可以旋轉。
Output:
輸出只有一行,包含一個數字,代表種類數量,請將此答案 % 1000000007 之後再輸出。
Sample Input:
3 5
101
010
101
000
000
000
010
000
100
Sample Output:
99
HINT:
對於範例測資,這是一種合理接法:

101 000 010 101 000
010 000 000 010 000
101 000 100 101 000

以下第二種範例,因為在第四、第五兩個醬油瓶之間存在一組汙漬相鄰因此就不合了:

101 000 010 101 010
010 000 000 010 000
101 000 100 101 100

醬油瓶是方形的O_O
Problem Setter
bigelephant29
Testdata:
TestTimeMemoryScore
01000ms65536kb
11000ms65536kb10
21000ms65536kb10
31000ms65536kb10
41000ms65536kb10
51000ms65536kb10
61000ms65536kb10
71000ms65536kb10
83000ms65536kb10
93000ms65536kb10
10-13000ms65536kb10
10-23000ms65536kb

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原