求各位大佬们 深信服这道笔试题怎么思考丫 没有一点思路

麻烦各位大佬们 提供一下思路吧 我太菜了

有一块土地，准备用来种果树，这块土地可以分割为N * M块，每一块种一颗果树。为了保证果树存活成长，需要避免两种情况:
1.相邻地块同时种植果树;
2.在岩石地块种植果树;

求共有多少种果树种植方式?

输入描述:

首行输入两个以空格分开的整数N，M (1<-N,M<=10)，接下来是N行每行M个整数.0表示该地块是岩石地块，不适合种植果树，1表示适合种植果树。

输入示例：
2 3
0 1 1
1 1 0

输出：
8

非常非常感谢评论区 大佬们不吝啬的解答(#^.^#) ！！
本小白经过一天的恶补 终于看懂了这道题的 状态压缩的方法！！！（虽然是入门题 但我已经费了九牛二虎之力 ┭┮﹏┭┮ ）
大家可以看一看这个博客：https://blog.csdn.net/harrypoirot/article/details/23163485
讲的很细致
还有@kxj000 提供的dfs方法：详见评论区 20楼