[HOJ 224]I. 棋盤

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

可以發現，只有斜邊連起來的點群會互相影響
然後，A和B只是把這些斜邊的長寬改變而已
所以我們只考慮A和B都是1的情況
首先，把矩形裡面的所有0(以下稱空格)都用-1和1填滿一定不會吃虧
考慮以下各種情形(線是邊界):
1 0 -1   0 0 1    |0 1
0 ? 0    0 ? 0    |? 0
1 0 0    1 0 0    |0 0
可以發現，在?填-1絕對是OK的(因為填1得分不可能更高)
因此，我們可以先用Bfs把所有可以用這種方式填出數字的空格都填一填
再來就剩以下情況了(線是邊界):
1 0 -1   1 0 0   0 0 0   |0 0   ____
0 ? 0    0 ? 0   0 ? 0   |? 0   |? 0
0 0 0    0 0 0   0 0 0   |0 0   |0 0
可以發現，只有第二種情況會攸關到「填-1，還是1」的抉擇
假如我們很Greedy的對每個獨立的空格群直接枚舉兩種數字交替的情形，取區域得分最高的
會不會有問題呢？
考慮以下的測資(為了格式美觀，+代表1，-代表-1，並且刪除了不相關的元素)
0 0 0 0
 0 0 0 0
- 0 0 0
 + 0 0 +
  + 0 - 
 - 0 + 
+ 0 0 +
 0 0 0 -
0 0 0 0
 0 0 0 0
如果我們把左上角填-1，其餘交替
- - - -
 + + + +
- - - - 
 + + + +
  + - - 
 - + + 
+ - - +
 + + + -
- - - -
 + + + +
得分是51
如果把左上角填1，其餘交替
得分也會是51
但我們有更好的填法:
- - - -
 + + + +
- - - -
 + + + +
  + - - 
 - - + 
+ + + +
 - - - -
+ + + +
 - - - -
得分變成54了！

所以，這個貪心法是錯誤的
怎麼解決呢？
我還沒想出來><
不過這個code可以得到90分，先展示囉XD~

最後有寫出可AC的code

code:

#include<cstdio>
typedef long long LL;
const LL MOD=1000000007LL;
int N,M;
struct Matrix
{
    LL s[10][10];
    Matrix(){}
    Matrix operator*(const Matrix &a)const
    {
        Matrix ans;
        for(int i=0;i<N;i++)for(int j=0;j<N;j++)
        {
            LL &v=ans.s[i][j]=0LL;
            for(int k=0;k<N;k++)(v+=(LL)s[i][k]*a.s[k][j])%=MOD;
        }
        return ans;
    }
};
char BOTTLE[11][3][4];
bool SpotInside(const int idx)
{
    for(int i=0;i<2;i++)for(int j=0;j<3;j++)if(BOTTLE[idx][i][j]=='1'&&BOTTLE[idx][i+1][j]=='1')return true;
    for(int i=0;i<3;i++)for(int j=0;j<2;j++)if(BOTTLE[idx][i][j]=='1'&&BOTTLE[idx][i][j+1]=='1')return true;
    return false;
}
Matrix Pow(Matrix a,int p)
{
    Matrix ans;
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)ans.s[i][j]=(i==j?(SpotInside(i)?0LL:1LL):0LL);
    while(p)
    {
        if(p&1)ans=ans*a;
        a=a*a;
        p>>=1;
    }
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        for(int i=0;i<N;i++)for(int j=0;j<3;j++)scanf("%s",BOTTLE[i][j]);
        Matrix m;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(SpotInside(i)||SpotInside(j)){m.s[i][j]=0LL;continue;}
                bool valid=true;
                for(int row=0;row<3;row++)if(BOTTLE[i][row][2]=='1'&&BOTTLE[j][row][0]=='1')
                {
                    valid=false;break;
                }
                m.s[i][j]=(valid?1LL:0LL);
            }
        }
//        for(int i=0;i<N;i++)
//        {
//            for(int j=0;j<N;j++)printf("%d ",m.s[i][j]);puts("");
//        }
        Matrix result=Pow(m,M-1);
        LL ans=0LL;
        for(int i=0;i<N;i++)for(int j=0;j<N;j++)(ans+=result.s[i][j])%=MOD;
        printf("%lld\n",ans);
    }
    return 0;
}