SGU 536 Berland Chess(状态压缩 + bfs)
在一个n*m的棋盘上，你有一个white king，然后还有一些(<15)个黑子，每个黑子有一定的攻击范围并且他们不会移动。求吃掉所有黑子的最少步数。黑子的个数很少，所以用状态压缩来表示棋盘上还剩余哪些黑子。在bfs前先要初始化所有黑子状态下的受攻击的点，这个很恶心。。。初始化完了基本就是无脑搜了吧？
#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<sstream>
#include<cstdlib>
#include<vector>
#include<string>
#include<cstdio>
#include<bitset>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
#define MP make_pair
using namespace std;
int dwx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dwy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dkx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dky[8] = {2, 1, -1, -2, -2, -1, 1, 2};
const int SET = (1<<15);
const int maxn = 20;
//can[sta][i][j] = 1 : 当前剩余sta中的黑子 点<i, j>不可走
//vis[sta][i][j] = 1 ：当前剩余sta中的黑子时，点<i, j>已走过
bool can[SET][maxn][maxn], vis[SET][maxn][maxn];
char g[maxn][maxn];
//id[x][y] ： 点<x, y>的黑子对应的标号
int n, m, sx, sy, tot, id[maxn][maxn];
inline bool outside(int x, int y)
{
return x<0 || x>=n || y<0 || y>=m;
}
//当前剩余sta中的黑子 点x y是否在sta中
inline bool has(int sta, int x, int y)
{
return isalpha(g[x][y]) && (sta & (1<<id[x][y]));
}
struct Node
{
int x, y, st, steps;
Node(){}
Node(int a, int b, int c, int d):x(a), y(b), st(c), steps(d){}
};
void bfs()
{
queue<Node> q; q.push(Node(sx, sy, tot, 0));
vis[tot][sx][sy] = 1;
while(!q.empty())
{
Node T = q.front(); q.pop();
if(T.st == 0)
{
printf("%d\n", T.steps);
return ;
}
REP(i, 8)
{
int tx = T.x + dwx[i], ty = T.y + dwy[i];
if(outside(tx, ty)) continue;
//如果当前状态 包含点<tx, ty>的黑子
if(has(T.st, tx, ty))
{
int sta = T.st&(tot-(1<<id[tx][ty]));
if(!vis[sta][tx][ty] && !can[sta][tx][ty])
//如果可以吃掉它
{
q.push(Node(tx, ty, sta, T.steps+1));
vis[sta][tx][ty] = 1;
}
}
else if(!can[T.st][tx][ty])
{
int sta = T.st;
if(!vis[sta][tx][ty])
{
q.push(Node(tx, ty, sta, T.steps+1));
vis[sta][tx][ty] = 1;
}
}
}
}
puts("-1");
return ;
}
//初始化所有状态下 会被攻击的点
void init()
{
FF(s, 1, tot+1)
{
//如果s状态下的黑子中 包含g[i][j] 那么更新g[i][j]的攻击范围
REP(i, n) REP(j, m) if(isalpha(g[i][j]) && (s & (1<<id[i][j])))
{
if(g[i][j] == 'K')
{
REP(k, 8)
{
int tx = i + dkx[k], ty = j + dky[k];
if(outside(tx, ty) || has(s, tx, ty)) continue;
can[s][tx][ty] = 1;
}
}
else if(g[i][j] == 'B')
{
int tx = i, ty = j;
while(true)
{
tx++, ty++;
if(outside(tx, ty) || has(s, tx, ty)) break;
can[s][tx][ty] = 1;
}
tx = i, ty = j;
while(true)
{
tx--, ty--;
if(outside(tx, ty) || has(s, tx, ty)) break;
can[s][tx][ty] = 1;
}
tx = i, ty = j;
while(true)
{
tx++, ty--;
if(outside(tx, ty) || has(s, tx, ty)) break;
can[s][tx][ty] = 1;
}
tx = i, ty = j;
while(true)
{
tx--, ty++;
if(outside(tx, ty) || has(s, tx, ty)) break;
can[s][tx][ty] = 1;
}
}
else
{
int tx = i, ty = j;
while(true)
{
tx++;
if(tx >= n || has(s, tx, ty)) break;
can[s][tx][ty] = 1;
}
tx = i, ty = j;
while(true)
{
tx--;
if(tx < 0 || has(s, tx, ty)) break;
can[s][tx][ty] = 1;
}
tx = i, ty = j;
while(true)
{
ty++;
if(ty>=m || has(s, tx, ty)) break;
can[s][tx][ty] = 1;
}
tx = i, ty = j;
while(true)
{
ty--;
if(ty<0 || has(s, tx, ty)) break;
can[s][tx][ty] = 1;
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
tot = 0;
REP(i, n)
{
scanf("%s", g[i]);
REP(j, m)
{
if(g[i][j] == '*') sx = i, sy = j;
else if(isalpha(g[i][j])) id[i][j] = tot++;
}
}
if(tot == 0)
{
puts("0");
return 0;
}
tot = (1<<tot)-1;
init();
bfs();
return 0;
}
补充：软件开发 , C++ ,
