結果
| 問題 |
No.226 0-1パズル
|
| コンテスト | |
| ユーザー |
 moricup
|
| 提出日時 | 2020-10-06 21:15:14 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 9,507 bytes |
| コンパイル時間 | 1,669 ms |
| コンパイル使用メモリ | 173,376 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-26 14:26:16 |
| 合計ジャッジ時間 | 2,427 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
//typedef
typedef unsigned int UINT;
typedef unsigned long long ULL;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef tuple<LL, LL, LL> TLL3;
typedef tuple<LL, LL, LL, LL> TLL4;
typedef set<LL, greater<LL> > setdownLL;
#define PQ priority_queue
typedef PQ<LL, vector<LL>, greater<LL> > pqupLL;
//container utill
#define ALL(v) (v).begin(),(v).end()
#define CR [](auto element1, auto element2){return element1>element2;}
#define LB lower_bound
#define UP upper_bound
#define PB push_back
#define MP make_pair
#define MT make_tuple
//constant
#define PI 3.141592653589793
const LL MOD=1000000007;
int main(){
//input
LL H,W;
cin >> H >> W;
string gri[H];
LL i,j,k;
for(i=0; i<H; i++){
cin >> gri[i];
}
bool vercan=1, horcan=1;
//find vertical from left to right
for(j=0; j<=W-2; j++){
for(i=0; i<H; i++){
if(gri[i][j]!='?'&&gri[i][j]==gri[i][j+1]){
horcan=0;
for(k=i-1; k>=0; k--){
if(gri[k][j]!='?'&&gri[k][j]==gri[k+1][j]){
cout << 0 << endl;
return 0;
}
if(gri[k][j+1]!='?'&&gri[k][j+1]==gri[k+1][j+1]){
cout << 0 << endl;
return 0;
}
if(gri[k+1][j]=='0'){
gri[k][j]='1';
gri[k][j+1]='1';
}else{
gri[k][j]='0';
gri[k][j+1]='0';
}
}
for(k=i+1; k<H; k++){
if(gri[k][j]!='?'&&gri[k][j]==gri[k-1][j]){
cout << 0 << endl;
return 0;
}
if(gri[k][j+1]!='?'&&gri[k][j+1]==gri[k-1][j+1]){
cout << 0 << endl;
return 0;
}
if(gri[k-1][j]=='0'){
gri[k][j]='1';
gri[k][j+1]='1';
}else{
gri[k][j]='0';
gri[k][j+1]='0';
}
}
break;
}
}
}
//find vertical from right to left
for(j=W-2; j>=0; j--){
for(i=0; i<H; i++){
if(gri[i][j]!='?'&&gri[i][j]==gri[i][j+1]){
horcan=0;
for(k=i-1; k>=0; k--){
if(gri[k][j]!='?'&&gri[k][j]==gri[k+1][j]){
cout << 0 << endl;
return 0;
}
if(gri[k][j+1]!='?'&&gri[k][j+1]==gri[k+1][j+1]){
cout << 0 << endl;
return 0;
}
if(gri[k+1][j]=='0'){
gri[k][j]='1';
gri[k][j+1]='1';
}else{
gri[k][j]='0';
gri[k][j+1]='0';
}
}
for(k=i+1; k<H; k++){
if(gri[k][j]!='?'&&gri[k][j]==gri[k-1][j]){
cout << 0 << endl;
return 0;
}
if(gri[k][j+1]!='?'&&gri[k][j+1]==gri[k-1][j+1]){
cout << 0 << endl;
return 0;
}
if(gri[k-1][j]=='0'){
gri[k][j]='1';
gri[k][j+1]='1';
}else{
gri[k][j]='0';
gri[k][j+1]='0';
}
}
break;
}
}
}
//find horizontal from up to down
for(i=0; i<=H-2; i++){
for(j=0; j<W; j++){
if(gri[i][j]!='?'&&gri[i][j]==gri[i+1][j]){
vercan=0;
for(k=j-1; k>=0; k--){
if(gri[i][k]!='?'&&gri[i][k]==gri[i][k+1]){
cout << 0 << endl;
return 0;
}
if(gri[i+1][k]!='?'&&gri[i+1][k]==gri[i+1][k+1]){
cout << 0 << endl;
return 0;
}
if(gri[i][k+1]=='0'){
gri[i][k]='1';
gri[i+1][k]='1';
}else{
gri[i][k]='0';
gri[i+1][k]='0';
}
}
for(k=j+1; k<W; k++){
if(gri[i][k]!='?'&&gri[i][k]==gri[i][k-1]){
cout << 0 << endl;
return 0;
}
if(gri[i+1][k]!='?'&&gri[i+1][k]==gri[i+1][k-1]){
cout << 0 << endl;
return 0;
}
if(gri[i][k-1]=='0'){
gri[i][k]='1';
gri[i+1][k]='1';
}else{
gri[i][k]='0';
gri[i+1][k]='0';
}
}
break;
}
}
}
//find horizontal from down to up
for(i=H-2; i>=0; i--){
for(j=0; j<W; j++){
if(gri[i][j]!='?'&&gri[i][j]==gri[i+1][j]){
vercan=0;
for(k=j-1; k>=0; k--){
if(gri[i][k]!='?'&&gri[i][k]==gri[i][k+1]){
cout << 0 << endl;
return 0;
}
if(gri[i+1][k]!='?'&&gri[i+1][k]==gri[i+1][k+1]){
cout << 0 << endl;
return 0;
}
if(gri[i][k+1]=='0'){
gri[i][k]='1';
gri[i+1][k]='1';
}else{
gri[i][k]='0';
gri[i+1][k]='0';
}
}
for(k=j+1; k<W; k++){
if(gri[i][k]!='?'&&gri[i][k]==gri[i][k-1]){
cout << 0 << endl;
return 0;
}
if(gri[i+1][k]!='?'&&gri[i+1][k]==gri[i+1][k-1]){
cout << 0 << endl;
return 0;
}
if(gri[i][k-1]=='0'){
gri[i][k]='1';
gri[i+1][k]='1';
}else{
gri[i][k]='0';
gri[i+1][k]='0';
}
}
break;
}
}
}
char num;
//check vertical
for(j=0; j<W; j++){
for(i=0; i<H; i++){
if(gri[i][j]!='?'){
num=gri[i][j];
for(k=i+1; k<H; k++){
if(gri[k][j]!='?'){
if(((k-i)%2)==0&&gri[k][j]!=gri[i][j]){
vercan=0;
}
if(((k-i)%2)==1&&gri[k][j]==gri[i][j]){
vercan=0;
}
}
}
i=H-1;
}
}
}
//check horizontal
for(i=0; i<H; i++){
for(j=0; j<W; j++){
if(gri[i][j]!='?'){
num=gri[i][j];
for(k=j+1; k<W; k++){
if(gri[i][k]!='?'){
if(((k-j)%2)==0&&gri[i][k]!=gri[i][j]){
horcan=0;
}
if(((k-j)%2)==1&&gri[i][k]==gri[i][j]){
horcan=0;
}
}
}
j=W-1;
}
}
}
bool zerotile=1, onetile=1;
//check zerotile
for(i=0; i<H; i++){
for(j=0; j<W; j++){
if(gri[i][j]!='?'){
if(gri[i][j]!='0'+((i+j)%2)){
zerotile=0;
}
}
}
}
//check onetile
for(i=0; i<H; i++){
for(j=0; j<W; j++){
if(gri[i][j]!='?'){
if(gri[i][j]!='0'+((i+j+1)%2)){
onetile=0;
}
}
}
}
LL ans=0, val;
bool que;
//add when vertical
if(vercan==1){
val=1;
for(j=0; j<W; j++){
que=1;
for(i=0; i<H; i++){
if(gri[i][j]!='?'){
que=0;
}
}
if(que==1){
val*=2;
val%=MOD;
}
}
ans+=val;
ans%=MOD;
}
//add when horizontal
if(horcan==1){
val=1;
for(i=0; i<H; i++){
que=1;
for(j=0; j<W; j++){
if(gri[i][j]!='?'){
que=0;
}
}
if(que==1){
val*=2;
val%=MOD;
}
}
ans+=val;
ans%=MOD;
}
//remove multiple
if(zerotile==1){
ans+=(MOD-1);
ans%=MOD;
}
if(onetile==1){
ans+=(MOD-1);
ans%=MOD;
}
//output
cout << ans << endl;
return 0;
}