台湾菜

HDOJ 2269 Cross The River

twcai • acm/icpc

广搜题again,本来不应该卡那么久,一个原因是逻辑不清楚,另一个原因就是位运算时犯错。
位运算是个好东东,如果某个计算过程会被大量用到,用位运算优化能够严重提高效率。但是位运算符有一个需要注意的地方就是他们的优先级都很低,除了左移右移(>>, <<)以外的几个位运算符甚至比比较运算符(比如==, >=, <=)还要低,而且位运算符之间也有优先级差别:依次为~, &, ^, |. 具体的优先级可以查阅这里:C++ Operator Precedence
正如软件工程课上所讲的:为了阅读上的需要,有时候加上冗余的括号也是很有必要的。

#include
#include
#include
#include
#include
#include
using namespace std;

int n, m, t, end;
int d[110];
bool hash[3000][2];
map mm;
vector vv;
vector vn;

struct node{
int sta[2], no[2], np, t;
};
queue qq;

inline void dfs(int sta, int chosen, int x, int y){
if(y == t || x == n){
vv.push_back(chosen);
vn.push_back(y);
}
else{
if(sta & (1 << x))
dfs(sta, chosen | (1 << x), x +1, y +1);
dfs(sta, chosen, x +1, y);
}
}

inline int bfs()
{
int i, j, k;
bool fg;
end = (1 << n) - 1;
while(!qq.empty()) qq.pop();
memset(hash, 0, sizeof(hash));
hash[0][1] = 1;
node now, next;
now.np = 1, now.t = 0;
now.sta[0] = 0, now.sta[1] = end;
now.no[0] = 0, now.no[1] = n;
qq.push(now);

while(!qq.empty())
{
now = qq.front(), qq.pop();
if(now.sta[0] == end)
return now.t;
if(now.no[1] <= t && now.np == 1){
next.no[0] = n;
next.no[1] = 0;
next.sta[0] = end;
next.sta[1] = 0;
next.t = now.t + 1;
next.np = 1 - now.np;
hash[next.sta[0]][next.np] = 1;
qq.push(next);
continue;
}
else{
vv.clear(), vn.clear();
dfs(now.sta[now.np], 0, 0, 0);
for(i = 0; i < vv.size(); i++){
next.sta[1 -now.np] = now.sta[1 -now.np] | vv[i];
next.sta[now.np] = now.sta[now.np] & (~vv[i]);
fg = 1;
for(j = 0; j < m; j++){
if((d[j] & next.sta[now.np]) == d[j]){
//Here is my mistake
//I wrote (d[j] & next.sta[now.np] == d[j]) at first
fg = 0;
break;
}
}
if(!fg) continue;
next.np = 1 - now.np;
if(hash[next.sta[0]][next.np]) continue;
next.no[next.np] = now.no[next.np] + vn[i];
next.no[now.np] = now.no[now.np] - vn[i];
next.t = now.t + 1;
hash[next.sta[0]][next.np] = 1;
qq.push(next);
}
}
}
return -1;
}

int main()
{
int i, ret;
char ts[30], ln[1010];
string name;
while(scanf("%d %d %d", &n, &m, &t) != EOF)
{
mm.clear();
for(i = 0; i < n; i++){
scanf("%s", ts);
name = ts;
mm[name] = i;
}
gets(ln);
for(i = 0; i < m; i++){
gets(ln);
d[i] = 0;
int ct = 0;
while(ln[ct] != '\0'){
sscanf(ln + ct, "%s", ts);
name = ts;
d[i] |= 1 << mm[name];
ct += name.length();
for(; ln[ct] == ' '; ct++);
}
}

ret = bfs();
printf("%d\n", ret);
}
return 0;
}

/*
3 1 1
cab
sheep
wolf
cab
*/

comments powered by Disqus