結果
| 問題 |
No.460 裏表ちわーわ
|
| ユーザー |
 kuuso1
|
| 提出日時 | 2016-12-11 04:45:58 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,148 bytes |
| コンパイル時間 | 3,168 ms |
| コンパイル使用メモリ | 112,256 KB |
| 実行使用メモリ | 23,552 KB |
| 最終ジャッジ日時 | 2025-01-08 12:00:09 |
| 合計ジャッジ時間 | 16,217 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 27 TLE * 1 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
class TEST{
static void Main(){
Sol mySol =new Sol();
mySol.Solve();
}
}
class Sol{
public void Solve(){
int[] a0 = new int[H];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(A[i][j] == 1){
a0[i] |= (1<<j);
}
}
}
Min = 9999;
fm = (1<<W)-1;
int[] r = Enumerable.Repeat(-1,H).ToArray();
dfs(a0,r,-1);
Console.WriteLine(Min == 9999 ? "Impossible" : Min.ToString());
}
int Min;
int fm;
int cnt = 0;
void dfs(int[] Mp, int[] route, int dep){
if(dep == H-1){
for(int i=0;i<H;i++) if(Mp[i] != 0) return;
int tot = 0;
for(int i=0;i<H;i++) tot += PopCnt(route[i]);
Min = Math.Min(Min,tot);
cnt++;
return;
}
dep++;
for(int i=0;i<(1<<W);i++){
int lm = 0;
for(int j=0;j<W;j++){
if(((i>>j) & 1) == 1){
lm ^= j == 0 ? 3 : (7<<(j-1));
}
}
lm &= fm;
int[] nMp = (int[]) Mp.Clone();
for(int j=dep-1;j<=dep+1;j++){
if(j<0 || j>=H)continue;
nMp[j] ^= lm;
}
if(dep-1>=0){
if(nMp[dep-1] == 0){
var r = (int[])route.Clone();
r[dep] = i;
int tt = 0; for(int j=0;j<H;j++) if(r[j]!=-1) tt += PopCnt(r[j]);
if(tt <= Min)dfs(nMp,r,dep);
}
}else{
var r = (int[])route.Clone();
r[dep] = i;
int tt = 0; for(int j=0;j<H;j++) if(r[j]!=-1) tt += PopCnt(r[j]);
if(tt <= Min)dfs(nMp,r,dep);
}
}
}
int PopCnt(int bits){
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}
int H,W;
int[][] A;
public Sol(){
using( var r = new FastIn()){
H = r.ReadInt();
W = r.ReadInt();
A = new int[H][];
for(int i=0;i<H;i++) A[i] = new int[W];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
A[i][j] = r.ReadInt();
}
}
}
}
static String rs(){return Console.ReadLine();}
static int ri(){return int.Parse(Console.ReadLine());}
static long rl(){return long.Parse(Console.ReadLine());}
static double rd(){return double.Parse(Console.ReadLine());}
static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}
class FastIn:IDisposable {
int Size;
byte[] Mem;
int ptr;
int rsize;
bool unfinished;
Stream stdin;
void Init(int n) {
Size = n;
Mem = new byte[Size];
rsize=(stdin=Console.OpenStandardInput()).Read(Mem, 0, Size);
ptr = 0;
unfinished=(rsize == Size);
}
void Next() {
if (unfinished == false) return;
rsize=stdin.Read(Mem, 0, Size);
ptr = 0;
unfinished = (rsize == Size);
}
~FastIn(){
stdin.Dispose();
}
void IDisposable.Dispose(){
stdin.Dispose();
}
public void Dispose(){
stdin.Dispose();
}
public FastIn() {
Init(100000);
}
public FastIn(int n) {
Init(n);
}
public int ReadInt() {
int ret = 0;
int sig = 1;
while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) {
if(ret==0 && Mem[ptr] == '-'){
sig *= -1; ptr++; continue;
}
ret = ret * 10 + Mem[ptr++] - '0';
if (ptr == Size) Next();
}
while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) {
ptr++;
if (ptr == Size) Next();
}
return ret*sig;
}
public uint ReadUint() {
uint ret = 0;
uint sig = 1;
while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) {
ret = ret * 10 + Mem[ptr++] - '0';
if (ptr == Size) Next();
}
while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) {
ptr++;
if (ptr == Size) Next();
}
return ret*sig;
}
public long ReadLong() {
long ret = 0;
long sig = 1;
while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) {
if(ret==0 && Mem[ptr] == '-'){
sig *= -1; ptr++; continue;
}
ret = ret * 10 + Mem[ptr++] - '0';
if (ptr == Size) Next();
}
while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) {
ptr++;
if (ptr == Size) Next();
}
return ret*sig;
}
public double ReadDouble() {
double ret = 0;
double sig = 1;
bool dot = false;
double keta = 0.1;
while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) {
if(ret==0 && Mem[ptr] == '-'){
sig *= -1; ptr++;
if (ptr == Size) Next();
continue;
}
if(Mem[ptr] == '.'){
dot = true;
ptr++;
if (ptr == Size) Next();
continue;
}
if(!dot){
ret = ret * 10 + Mem[ptr++] - '0';
if (ptr == Size) Next();
}else{
ret = ret + (Mem[ptr++] - '0')*keta;
keta /= 10.0;
if (ptr == Size) Next();
}
}
while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) {
ptr++;
if (ptr == Size) Next();
}
return ret*sig;
}
public String ReadStr() {
//2byte文字はNG
StringBuilder sb = new StringBuilder();
while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r') {
sb.Append((char)Mem[ptr++]);
if (ptr == Size && unfinished) Next();
}
while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) {
ptr++;
if (ptr == Size && unfinished) Next();
}
return sb.ToString();
}
public String ReadLine() {
//極力使わない(split/parseするくらいなら上をつかう）
StringBuilder sb = new StringBuilder();
while (ptr < rsize && Mem[ptr] != '\n' && Mem[ptr] != '\r') {
sb.Append((char)Mem[ptr++]);
if (ptr == Size && unfinished) Next();
}
while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r')) {
ptr++;
if (ptr == Size && unfinished) Next();
}
return sb.ToString();
}
}