| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
递归法枚举,时间125ms,最菜的做法#include<iostream>
#include<stdio.h>
using namespace std;
bool Check(bool maps[4][4])
{
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (maps[i][j] != maps[0][0])
{
return false;
}
}
}
return true;
}
void Flip(int index, bool maps[4][4])
{
int r = index / 4;
int c = index % 4;
if (r > 0)
{
maps[r - 1][c] = !maps[r - 1][c];
}
if (r < 3)
{
maps[r + 1][c] = !maps[r + 1][c];
}
if (c > 0)
{
maps[r][c - 1] = !maps[r][c - 1];
}
if (c < 3)
{
maps[r][c + 1] = !maps[r][c + 1];
}
maps[r][c] = !maps[r][c];
}
void Solution(int index,bool maps[4][4],int count,int &min)
{
if (index == 16)
{
if (Check(maps)&&min > count )
{
min = count;
}
return;
}
bool temp[4][4];
memset(temp, true, 16);
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
temp[i][j] = maps[i][j];
}
}
Solution(index + 1, temp,count,min);
Flip(index, temp);
Solution(index + 1, temp,count+1,min);
}
int main()
{
char map[4][5];
bool maps[4][4];
memset(maps, true, 16);
char n;
while (~scanf("%20c", map,map+1,map+2,map+3, map + 4, map + 5, map + 6, map + 7, map + 8, map + 9, map + 10, map + 11, map + 12, map + 13, map + 14, map + 15,map+16,map+17,map+18,map+19 ))
{
int count = 0;
int min = 17;
bool flag = true;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (map[i][j] != map[0][0])
{
flag = false;
}
if (map[i][j] == 'w')
{
maps[i][j] = true;
}
else
{
maps[i][j] = false;
}
}
}
Solution(0, maps, count, min);
if (min == 17)
{
cout << "Impossible" << endl;
}
else if (!flag)
{
Solution(0, maps, count, min);
cout << min<<endl;
}
else
{
cout << "0"<<endl;
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator