abstract：
這是一隻碼狗企圖用代碼在朋友圈掀起一場腥風血雨的慘痛失敗的小記。。。。。。。。。
這是一個陽光明媚的下午，我吃着火鍋唱着歌，徜徉在我平靜的朋友圈，突然，幾行小字閃電般刺痛了我的狗眼，大概是這樣式的：
作為這種無腦遊戲的狂熱愛好者，我怎！麼！能！忍！裝B也要按照基本法啊！
于是我：
①截圖
②python腳本擷取元素RGB
③取餘求平均RGB，識别顔色，顔色矩陣轉數組
④分支限界搜尋最優解
有一大坑：圖用python縮略後，RGB出現很多嚴重偏離的像素點，不知為何。就因為這，識别步驟花了很長時間。
搞出顔色數組，樹搜尋一跑，卒。
計算量太大了，采用的剪枝政策太naive，又想不出更高明政策，裝B失敗，還困的不行。。。。
顔色識别代碼：
# -*- coding: utf-8 -*-
import colorsys
import Image
import sys
def getDiff(colorRGB, r, g, b):
diff = 0;
diff = max(abs(colorRGB[0] - r), diff)
diff = max(abs(colorRGB[1] - g), diff)
diff = max(abs(colorRGB[2] - b), diff)
return diff
def getColorId(r, g, b):
dic = { "red":(275, 80, 80),
"orange":(241, 163, 13),
"green":(181, 207, 38),
"blue":(36, 168, 236),
"purple":(180, 80, 227)}
color_id = { "red":1, "orange":2, "green":3, "blue":4, "purple":5 }
min_diff = sys.maxint
result = -1
for color in dic:
diff = getDiff(dic[color], r, g, b)
if diff < min_diff:
#最小偏離值
result = color_id[color]
min_diff = diff
return result
def get_dominant_color(path):
board = [[0 for col in range(10)] for row in range(10)]
image = Image.open(path)
pix = image.load()
for i in range(0, 10):
n =16*2 + i*(345/10)*2
for j in range(0, 10):
m = 159*2 + j*(343/10)*2
count_r = 0
count_g = 0
count_b = 0
count =0
for aa in range(0,34*2):
for bb in range(0, 34*2):
r, g, b = pix[n+aa, m+bb]
if r+g+b<600: #去除噪聲
count += 1
count_r += r
count_g += g
count_b += b
color_id = getColorId(count_r/count, count_g/count, count_b/count)
board[j][i] = color_id
return board
if __name__=="__main__":
path = "C:\\Users\\go2sea\\Desktop\\test\\IMG_6131.PNG"
fp = open('file_color.txt','w')
board = get_dominant_color(path)
print "{",
for ii in range(len(board)):
line = board[ii]
print "{ ",
for i in range(len(line)):
print line[i],
if i != len(line)-1:
print", ",
print "}",
if ii!=len(board)-1:
print","
print "};"
fp.close()
搜尋代碼：
#pragma once
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
//pq中優先級的比較
struct Compare {
//傳回 block1優先級低于block2優先級
bool operator () (pair<vector<pair<int, int>>, pair<int, int>> pair1, pair<vector<pair<int, int>>, pair<int, int>> pair2) {
//return pair1.first.size() < pair2.first.size();
return pair1.first.size() > pair2.first.size();
}
};
void printBoard(vector<vector<int>>& board) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++)
cout << board[i][j] << " ";
cout << endl;
}
cout << endl;
}
int maxPointsRest(vector<vector<int>>& board) {
map<int, int> m;
for (auto v : board)
for (auto c : v)
if (c > 0)
m[c]++;
int result = 0;
for (auto p : m)
if (p.second>1)
result += pow(p.second, 2);
return result;
}
//保證[i, j]位置不為0
vector<pair<int, int>> getBlock(vector<vector<int>> board, int i, int j) {
vector<pair<int, int>> block;//色塊，初值隻有一個格子[i,j]
block.push_back(pair<int, int>(i, j));
int color = board[i][j];//記錄顔色
board[i][j] = 0;//現有block染黑
while (true) {
int size_before = block.size();
for (int m = 0; m < board.size(); m++){
for (int n = 0; n < board[0].size(); n++) {
if (board[m][n] != color)
continue;
for (auto p : block) {
int i = p.first, j = p.second;
if (abs(i - m) + abs(j - n) != 1)
continue;
block.push_back(pair<int, int>(m, n));
board[m][n] = 0; //染黑
break;
}
}
}
if (block.size() == size_before)
return block;
}
}
//将block中格子置0（染黑）
void setBlack(vector<vector<int>>& board, vector<pair<int, int>>& block) {
if (block.empty())
return;
int color = board[block[0].first][block[0].second];
for (auto p : block) {
assert(color == board[p.first][p.second]);
board[p.first][p.second] = 0;
}
}
//已染黑，落子（向左下角縮）
void shape(vector<vector<int>>& board) {
//每一列，從下往上，落到底，同時記錄那一列為空
vector<bool> empty_column(board[0].size(), false);
for (int j = 0; j < board[0].size(); j++) {
int slow = board.size() - 1;
while (slow >= 0 && board[slow][j] != 0) //尋找第一個空格子
slow--;
int fast = slow - 1;
while (fast >= 0) {
if (!board[fast][j]) {
fast--;
continue;
}
board[slow--][j] = board[fast][j];
board[fast--][j] = 0;
}
empty_column[j] = (slow == board.size() - 1); //該列是否為空
}
//從左邊第一個空列開始，他右面的落到相應位置，隻需一次周遊即可
int slow = 0;
while (slow < board[0].size() && !empty_column[slow]) //尋找第一個空列
slow++;
int fast = slow + 1;
while (fast < board[0].size()) {
if (empty_column[fast]) {
fast++;
continue;
}
//fast列拷貝到slow列
for (int index = 0; index < board.size(); index++)
board[index][slow] = board[index][fast], board[index][fast] = 0;
slow++, fast++;
}
}
//設定flag，表示某位置已劃入某一block，不再對其getBlock操作
void setFlag(vector<vector<int>>& board_flag, vector<pair<int, int>>& block) {
for (auto p : block) {
assert(board_flag[p.first][p.second] == 0);
board_flag[p.first][p.second] = 1;
}
}
//保證i,j可點，即getBlock(board, i, j)傳回的block大小總>1（注意，now_path已經包含了生成該block所點選的[i, j]
void pointAt(vector<vector<int>> board, vector<pair<int, int>> block, int& max_score, int now_score, vector<pair<int, int>>& min_path, vector<pair<int, int>> now_path) {
setBlack(board, block);
shape(board);
now_score += pow(block.size(), 2);
//剪枝
if (maxPointsRest(board) + now_score <= max_score)
return;
bool end_status = true;
//找所有的block，放入pq中
priority_queue<pair<vector<pair<int, int>>, pair<int, int>>, vector < pair<vector<pair<int, int>>, pair<int, int>> >, Compare> pq;
vector<vector<int>> board_flag(board.size(), vector<int>(board[0].size(), 0)); //某位置為1表示已劃分入某個block，不再對其getBlock
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (board_flag[i][j] == 1 || board[i][j] == 0)
continue;
block = getBlock(board, i, j);
if (block.size() == 1) continue;
pq.push(pair<vector<pair<int, int>>, pair<int, int>>(block, pair<int, int>(i, j)));
setFlag(board_flag, block);
end_status = false;
}
}
while (!pq.empty()) {
block = pq.top().first;
pair<int, int> location = pq.top().second;
pq.pop();
now_path.push_back(location);
pointAt(board, block, max_score, now_score, min_path, now_path);
}
if (end_status && now_score > max_score)
max_score = now_score, min_path = now_path;
}
void search(vector<vector<int>> board) {
int max_score = 0;
vector<pair<int, int>> min_path;
vector<pair<int, int>> now_path;
vector<pair<int, int>> block;
pointAt(board, block, max_score, 0, min_path, now_path);
cout << "min_path:" << endl;
for (auto p : min_path)
cout << "[" << p.first << ", " << p.second << "] " << endl;
cout << "max_score: " << max_score << endl;
}
void main() {
//vector<vector<int>> board =
//{ { 4, 3, 3, 4, 4, 1, 2, 5, 2, 5 },
//{ 5, 3, 1, 2, 1, 4, 1, 1, 2, 5 },
//{ 3, 1, 1, 2, 2, 3, 1, 1, 4, 5 },
//{ 3, 1, 1, 3, 3, 4, 3, 3, 4, 5 },
//{ 3, 1, 3, 1, 4, 3, 1, 3, 4, 4 },
//{ 1, 4, 2, 4, 4, 3, 5, 4, 1, 4 },
//{ 1, 2, 4, 2, 4, 4, 3, 3, 1, 1 },
//{ 4, 2, 4, 4, 4, 4, 3, 2, 1, 2 },
//{ 4, 3, 3, 4, 4, 4, 3, 2, 1, 2 },
//{ 4, 3, 4, 4, 3, 4, 3, 2, 1, 2 } };
//vector<vector<int>> board = { { 1, 3, 4, 1, 2, 4, 3, 1, 1, 3 },
//{ 1, 3, 5, 1, 1, 4, 3, 1, 1, 4 },
//{ 2, 5, 1, 1, 1, 3, 3, 5, 1, 4 },
//{ 1, 3, 1, 4, 3, 4, 3, 1, 4, 2 },
//{ 3, 3, 1, 5, 3, 1, 3, 1, 4, 2 },
//{ 3, 4, 2, 5, 1, 2, 4, 4, 4, 3 },
//{ 3, 3, 2, 1, 1, 2, 2, 4, 3, 3 },
//{ 3, 1, 2, 1, 3, 3, 4, 3, 5, 4 },
//{ 4, 2, 3, 1, 4, 3, 1, 3, 2, 4 },
//{ 4, 4, 1, 5, 4, 3, 4, 1, 2, 4 } };
//vector<vector<int>> board = { { 1, 3, 4, 1, 2, 4 },
//{ 1, 3, 5, 1, 1, 4 },
//{ 2, 5, 1, 1, 1, 3 },
//{ 1, 3, 1, 4, 3, 4 },
//{ 3, 3, 1, 5, 3, 1},
//{ 3, 4, 2, 5, 1, 2} };
//vector<vector<int>> board = { { 1, 3, 4, 1},
//{ 1, 3, 5, 1},
//{ 2, 5, 1, 1},
//{ 1, 3, 1, 4} };
vector<vector<int>> board = { { 1, 3, 4, 1, 2 },
{ 1, 3, 5, 1, 1 },
{ 2, 5, 1, 1, 1 },
{ 1, 3, 1, 4, 3 },
{ 3, 3, 1, 5, 3 } };
search(board);
system("pause");
}