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