搜索 P1312 【Mayan游戏】
思路跟楼下一样，但是用map存了状态，防止状态相同，从原来的2000ms到400ms，还挺快的。
还有一个不同就是把棋盘写进一个结构体，看起来比较舒服emmmmmm...
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <stack>
using namespace std;
struct board
{
int p[5][7];
inline void print()
{
for(int i(0);i < 5;++i)
{
for(int j(0);j < 7;++j)
{
printf("%d\t",p[i][j]);
}
printf("\n");
}
printf("\n");
return;
}
inline void read()
{
memset(p,0,sizeof(p));
for(int i(0);i < 5;++i)
{
for(int j(0);j < 7;++j)
{
scanf("%d",&p[i][j]);
if(p[i][j] == 0)break;
if(j == 6)scanf("%*d");
}
}
}
inline void down(int line)
{
for(int i(1);i < 7;++i)
{
if(p[line][i] == 0)continue;
int pos(i);
while(p[line][pos - 1] == 0 && pos > 0)
{
p[line][pos - 1] = p[line][pos];
p[line][pos] = 0;
--pos;
}
}
}
inline bool empty()
{
for(int i(0);i < 5;++i)if(p[i][0] != 0)return false;
return true;
}
inline void swap(int x1,int y1,int x2,int y2)
{
if(p[x1][y1] == p[x2][y2])return;
p[x1][y1] ^= p[x2][y2];
p[x2][y2] ^= p[x1][y1];
p[x1][y1] ^= p[x2][y2];
if(p[x1][y1] == 0 || p[x2][y2] == 0)
{
down(x1);
down(x2);
}
}
inline bool clear()
{
bool cls[5][7];
bool k(false);
for(int i(0);i < 5;++i)
{
for(int j(0);j < 7;++j)
{
cls[i][j] = false;
}
}
for(int i(0);i < 5;++i)
{
int now(0);
for(int j(1);j < 7;++j)
{
if(p[i][j] == 0)break;
if(p[i][j] != p[i][now]){now = j;continue;}
if(j - now == 2){k = true;for(int k(now);k <= j;++k)cls[i][k] = true;}
if(j - now > 2)cls[i][j] = true;
}
}
for(int i(0);i < 7;++i)
{
int now(0);
for(int j(1);j < 5;++j)
{
if(p[j][i] == 0){now = j + 1;continue;}
if(p[j][i] != p[now][i]){now = j;continue;}
if(j - now == 2){k = true;for(int k(now);k <= j;++k)cls[k][i] = true;}
if(j - now > 2)cls[j][i] = true;
}
}
if(k)
{
for(int i(0);i < 5;++i)
{
bool e(false);
for(int j(0);j < 7;++j)
{
if(cls[i][j])
{
e = true;
p[i][j] = 0;
}
}
if(e)down(i);
}
return true;
}
return false;
}
bool operator < (const board &a)const
{
for(int i(0);i < 5;++i)
{
for(int j(0);j < 7;++j)
{
if(p[i][j] != a.p[i][j])return p[i][j] < a.p[i][j];
}
}
return false;
}
};
stack <pair<pair<int,int>,int> > ans;
map <board,bool> used[10];
int n;
inline bool dfs(int step,board now)
{
if(n < step)
{
return now.empty();
}
if(used[step][now])return false;
used[step][now] = 1;
//没错就多了这两行代码
int tot[11];
memset(tot,0,sizeof(tot));
for(int i(0);i < 5;++i)for(int j(0);j < 7;++j)++tot[now.p[i][j]];
for(int i(1);i <= 10;++i)if(tot[i] && tot[i] < 3)return false;
//这是另一个优化，假如有一个数字小于2个就跳出，实际效果并不好，对于极端数据可能有优势
int i(0),j;
board tmp;
for(j = 0;j < 7;++j)
{
if(now.p[0][j] == 0)break;
tmp = now;
tmp.swap(0,j,1,j);
while(tmp.clear());
if(dfs(step + 1,tmp))
{
ans.push(make_pair(make_pair(0,j),1));
return true;
}
}
for(int i(1);i < 4;++i)
{
for(int j(0);j < 7;++j)
{
if(now.p[i][j] == 0)break;
tmp = now;
tmp.swap(i,j,i+1,j);
while(tmp.clear());
if(dfs(step + 1,tmp))
{
ans.push(make_pair(make_pair(i,j),1));
return true;
}
if(now.p[i - 1][j] == 0)
{
tmp = now;
tmp.swap(i,j,i-1,j);
while(tmp.clear());
if(dfs(step + 1,tmp))
{
ans.push(make_pair(make_pair(i,j),-1));
return true;
}
}
}
}
for(int j(0);j < 7;++j)
{
if(now.p[4][j] == 0)break;
if(now.p[3][j] == 0)
{
tmp = now;
tmp.swap(4,j,3,j);
while(tmp.clear());
if(dfs(step + 1,tmp))
{
ans.push(make_pair(make_pair(4,j),-1));
return true;
}
}
}
return false;
}
int main()
{
scanf("%d",&n);
board start;
start.read();
if(dfs(1,start))
{
while(!ans.empty())
{
pair<pair<int,int>,int> tmp;
tmp = ans.top();
printf("%d %d %d\n",tmp.first.first,tmp.first.second,tmp.second);
ans.pop();
}
}
else printf("-1\n");
return 0;
}