登 录
第一次使用双向广搜算法求解，感觉效率的确提高了不止两倍。刚开始的一直WA，后来发现是每次都要扩展一层的节点，然后在扩展另一层的节点，而不是每次只扩展一个节点。
/*<br /> Author: ACb0y<br /> Date: 2010-9-21<br /> Type: bbfs(双向广搜)<br /> ProblemId: hdu 1195 Open the Lock<br /> Result: AC<br /> */<br /> #include <iostream><br /> #include <queue><br /> using namespace std;</p> <p>struct node {<br /> char digit[5];<br /> int step;<br /> };</p> <p>int n;<br /> //初始化状态搜索标记数组(标记要达到某种状态需要的步数)<br /> int mark1[11][11][11][11];<br /> //最终状态搜索标记数组(标记要达到某种状态需要的步数)<br /> int mark2[11][11][11][11];<br /> //初始状态<br /> char a[5];<br /> //最终状态<br /> char b[5];</p> <p>void bbfs() {<br /> int i;<br /> //初始化标记数组<br /> memset(mark1, -1, sizeof(mark1));<br /> memset(mark2, -1, sizeof(mark2));<br /> //广搜使用的队列<br /> queue<node> Q1;<br /> queue<node> Q2;<br /> node cur, q, temp;<br /> strcpy(q.digit, a);<br /> q.step = 0;<br /> Q1.push(q);</p> <p> strcpy(q.digit, b);<br /> q.step = 0;<br /> Q2.push(q);<br /> int flag = 1;<br /> //用来标记当前的步数<br /> int pre1 = 0;<br /> int pre2 = 0;<br /> while (1) {<br /> //用广度优先扩展一层正向的节点如果发现扩展出来的节点在反向节点中出现则输出结果<br /> while (!Q1.empty() && Q1.front().step == pre1) {<br /> int k;<br /> cur = Q1.front();<br /> Q1.pop();<br /> //如果当前的状态没有被标记，则标记<br /> if (mark1[cur.digit[0] - '0'][cur.digit[1] - '0'][cur.digit[2] - '0'][cur.digit[3] - '0'] == -1)<br /> mark1[cur.digit[0] - '0'][cur.digit[1] - '0'][cur.digit[2] - '0'][cur.digit[3] - '0'] = cur.step;<br /> //扩展出来的节点在反向节点中出现，则输出答案<br /> k = mark2[cur.digit[0] - '0'][cur.digit[1] - '0'][cur.digit[2] - '0'][cur.digit[3] - '0'];<br /> if (k != -1) {<br /> printf("%d/n", cur.step + k);<br /> return;<br /> }</p> <p> //扩展节点，有三种扩展方式，加一，减一，交换相邻的数<br /> for (i = 0; i < 4; i++) {<br /> //加一<br /> strcpy(temp.digit, cur.digit);<br /> temp.digit[i]++;<br /> if (temp.digit[i] == '9' + 1) {<br /> temp.digit[i] = '1';<br /> }<br /> temp.step = cur.step + 1;<br /> //扩展出来的节点在反向节点中出现，则输出答案<br /> k = mark2[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'];<br /> if (k != -1) {<br /> printf("%d/n", temp.step + k);<br /> return;<br /> } else {<br /> if (mark1[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] == -1) {<br /> mark1[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] = temp.step;<br /> Q1.push(temp);<br /> }<br /> }</p> <p> //减一<br /> strcpy(temp.digit, cur.digit);<br /> temp.digit[i]--;<br /> if (temp.digit[i] == '0') {<br /> temp.digit[i] = '9';<br /> }<br /> temp.step = cur.step + 1;<br /> //扩展出来的节点在反向节点中出现，则输出答案<br /> k = mark2[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'];<br /> if (k != -1) {<br /> printf("%d/n", temp.step + k);<br /> return;<br /> } else {<br /> if (mark1[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] == -1) {<br /> mark1[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] = temp.step;<br /> Q1.push(temp);<br /> }<br /> }<br /> //交换位置<br /> if (i < 3) {<br /> strcpy(temp.digit, cur.digit);<br /> temp.digit[i] = cur.digit[i + 1];<br /> temp.digit[i + 1] = cur.digit[i];<br /> if (strcmp(temp.digit, cur.digit) != 0) {<br /> temp.step = cur.step + 1;<br /> //扩展出来的节点在反向节点中出现，则输出答案<br /> k = mark2[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'];<br /> if (k != -1) {<br /> printf("%d/n", temp.step + k);<br /> return;<br /> } else {<br /> if (mark1[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] == -1) {<br /> mark1[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] = temp.step;<br /> Q1.push(temp);<br /> }<br /> }<br /> }<br /> }<br /> }<br /> }<br /> pre1 = Q1.front().step;<br /> //用广度优先算法扩展一层反向节点，如果发现扩展出来的节点在正向节点中出现过，则输出结果<br /> while (!Q2.empty() && Q2.front().step == pre2) {<br /> int k;<br /> cur = Q2.front();<br /> Q2.pop();<br /> k = mark1[cur.digit[0] - '0'][cur.digit[1] - '0'][cur.digit[2] - '0'][cur.digit[3] - '0'];<br /> if (k != -1) {<br /> printf("%d/n", cur.step + k);<br /> return;<br /> }</p> <p> for (i = 0; i < 4; i++) {<br /> //加一<br /> strcpy(temp.digit, cur.digit);<br /> temp.digit[i]++;<br /> if (temp.digit[i] == '9' + 1) {<br /> temp.digit[i] = '1';<br /> }<br /> temp.step = cur.step + 1;<br /> k = mark1[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'];<br /> if (k != -1) {<br /> printf("%d/n", temp.step + k);<br /> return;<br /> } else {<br /> if (mark2[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] == -1) {<br /> mark2[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] = temp.step;<br /> Q2.push(temp);<br /> }<br /> }</p> <p> //减一<br /> strcpy(temp.digit, cur.digit);<br /> temp.digit[i]--;<br /> if (temp.digit[i] == '0') {<br /> temp.digit[i] = '9';<br /> }<br /> temp.step = cur.step + 1;<br /> k = mark1[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'];</p> <p> if (k != -1) {<br /> printf("%d/n", temp.step + k);<br /> return;<br /> } else {<br /> if (mark2[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] == -1) {<br /> mark2[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] = temp.step;<br /> Q2.push(temp);<br /> }<br /> }<br /> //交换位置<br /> if (i < 3) {<br /> strcpy(temp.digit, cur.digit);<br /> temp.digit[i] = cur.digit[i + 1];<br /> temp.digit[i + 1] = cur.digit[i];<br /> if (strcmp(temp.digit, cur.digit) != 0) {<br /> temp.step = cur.step + 1;<br /> k = mark1[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'];<br /> if (k != -1) {<br /> printf("%d/n", temp.step + k);<br /> return;<br /> } else {<br /> if (mark2[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] == -1) {<br /> mark2[temp.digit[0] - '0'][temp.digit[1] - '0'][temp.digit[2] - '0'][temp.digit[3] - '0'] = temp.step;<br /> Q2.push(temp);<br /> }<br /> }<br /> }<br /> }<br /> }<br /> }<br /> pre2 = Q2.front().step;<br /> }<br /> }</p> <p>int main()<br /> {<br /> #ifndef ONLINE_JUDGE<br /> freopen("1195.txt", "r", stdin);<br /> #endif<br /> scanf("%d", &n);<br /> while (n--) {<br /> scanf("%s%s", a, b);<br /> bbfs();<br /> }<br /> return 0;<br /> }<br />
抱歉!评论已关闭.