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 |
不知道这样想对不对直接DFS,当走到一个房间时,取得该房间的所有钥匙,再把跟能用这把钥匙打开的门的两个房间连通,DFS代码如下,哪位大牛能不能指点指点,哪里错了 void dfs(int t) { int i, j, tkey, t1, t2; if(t == 0) //走到了room[0] { ok = 1; return ; } for(i = 0; i < dkey[t].cnt; i ++) //dkey[t].cnt表示room[t]中的钥匙个数 { tkey = dkey[t].s[i] - 'A'; //dkey[t].s[i]表示room[t]中的钥匙 t1 = key[tkey][0]; //key[tkey]表示钥匙tkey连接的两个房间 t2 = key[tkey][1]; if(t1 != -1 && t2 != -1) map[t1][t2] = map[t2][t1] = 1; } for(i = 0; i < n; i ++) { if(i == t || mark[i]) continue ; if(map[t][i]) { mark[i] = 1; dfs(i); mark[i] = 0; } } } //后面改成一个钥匙能打开多个门也错了 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator