网站流量超了,健康保险网站,网站数据库建设计划书,网页界面设计和素材P1379 八数码难题
八数码难题首先要进行有解性判定#xff0c;避免无解情况下盲目搜索浪费时间。
有解性判定
P10454 奇数码问题
题意简述
在一个 n n n \times n nn 的网格中进行#xff0c;其中 n n n 为奇数#xff0c; 1 1 1 个空格和 [ 1 , n 2 − 1 ] [1,n^2…P1379 八数码难题
八数码难题首先要进行有解性判定避免无解情况下盲目搜索浪费时间。
有解性判定
P10454 奇数码问题
题意简述
在一个 n × n n \times n n×n 的网格中进行其中 n n n 为奇数 1 1 1 个空格和 [ 1 , n 2 − 1 ] [1,n^2 - 1] [1,n2−1] 这 n 2 − 1 n^2 - 1 n2−1 个数不重不漏地分布在网格中。空格可与上下左右的数字交换位置。现给定两个奇数码游戏的局面判定是否存在一种移动空格的方式使得互相可达。
实际上八数码问题就是一个 n 3 n 3 n3 的奇数码游戏。
思路
将网格图转为长为 n 2 − 1 n^2 - 1 n2−1 的一维序列例如
5 2 8
1 3 _
4 6 7可记为 5 , 2 , 8 , 1 , 3 , 4 , 6 , 7 5 ,2,8,1,3,4,6,7 5,2,8,1,3,4,6,7 忽略空格。可以发现若左右移动空格该序列不变若上下移动空格例如
5 2 _
1 3 8
4 6 7序列变为 5 , 2 , 1 , 3 , 8 , 4 , 6 , 7 5,2,1,3,8,4,6,7 5,2,1,3,8,4,6,7 相当于把 8 8 8 往前移动了 n − 1 2 n - 1 2 n−12 位有两个数字到了 8 8 8 的后面那么这两个数字中原来与 8 8 8 形成逆序对的变成了非逆序对原来与 8 8 8 形成非逆序对的变成了逆序对。
进一步思考
1.若在位置发生变动的数中原有奇数个逆序对由于 n − 1 n - 1 n−1 是偶数那么原来也有奇数个非逆序对因此交换后逆序对的个数仍为奇数
2.若在位置发生变动的数中原有偶数个逆序对由于 n − 1 n - 1 n−1 是偶数那么原来也有偶数个非逆序对因此交换后逆序对的个数仍为偶数。
综上所述无论怎么交换逆序对个数的奇偶性不变因此可以比较初状态和末状态的逆序对用树状数组统计奇偶性是否相同方可判定是否有解。
代码实现
注意 0 0 0 不参与统计忘了这一点会 WA。
#include bits/stdc.husing namespace std;int n;int lowbit(int p){return p (-p);}void insert(int p,int x,vector int c){for(;p n;p lowbit(p))c[p] x;
} int query(int p,vector int c){int sum 0;for(;p;p - lowbit(p)) sum c[p];return sum;
}int main(){ios::sync_with_stdio(0);cin.tie(0);while(cin n){n n * n; vector int c(n 1,0);int x,ans1,ans2,cnt1,cnt2;cnt1 cnt2 ans1 ans2 0;for(int i 1;i n;i){cin x;if(!x) continue;cnt1;insert(x,1,c);ans1 cnt1 - query(x,c);}for(int i 0;i n;i) c[i] 0;for(int i 1;i n;i){cin x;if(!x) continue;cnt2; insert(x,1,c);ans2 cnt2 - query(x,c);} if(ans1 % 2){if(ans2 % 2) cout TAK endl;else cout NIE endl;}else{if(ans2 % 2) cout NIE endl;else cout TAK endl;}}return 0;
}A-star
其实本题不需要可行性判定但学一下也无妨。
设计估价函数 h ( s t a t e ) h(state) h(state) 表示当前状态所有数字与其目标位置的曼哈顿距离和即 h ( s t a t e ) ∑ i 1 8 ∣ x i − x t a r g e t ∣ ∣ y i − y t a r g e t ∣ h(state) \sum_{i 1}^{8} \left | x_i - x_{target} \right | \left | y_i - y_{target} \right | h(state)i1∑8∣xi−xtarget∣∣yi−ytarget∣ 显然实际操作数 g ( s t a t e ) ≥ h ( s t a t e ) g(state) \ge h(state) g(state)≥h(state) 因为 h h h 表示每个数字去目标点都走最短路而实际至少得走这么远 h h h 函数可采纳且较接近真实值相比之下“错位数”即不在目标位置的数字个数这一估价函数虽可采纳但大多数时候远小于真实值求解效率低最终入队的总代价即为 f g h f g h fgh 。
代码实现
#include bits/stdc.husing namespace std;const string TARGET 123804765;
const int dx[] {0,0,-1,1};
const int dy[] {-1,1,0,0};struct Node{string state;int g,h,f;Node(string s,int _g,int _h) :state(s),g(_g),h(_h),f(_g _h) {}//重载运算符bool operator (const Node other) const {return f other.f;}
};//预处理target状态坐标
void initTargetPos(unordered_map char,int pos_map){for(int i 0;i 9;i){char c TARGET[i];if(c ! 0) pos_map[c] i;}
} //函数求曼哈顿距离和
int mahattan(const string state,const unordered_map char,int pos_map){int distance 0;for(int i 0;i 9;i){char c state[i];if(c 0) continue;int target_pos pos_map.at(c);//当前数字坐标 int cur_x i % 3;int cur_y i / 3;//目标位置坐标 int tar_x target_pos % 3;int tar_y target_pos / 3;distance abs(cur_x - tar_x) abs(cur_y - tar_y);}return distance;
}int A_star(string start){if(start TARGET) return 0;//预处理目标位置 unordered_map char,int pos_map;initTargetPos(pos_map);priority_queue Node open_list;unordered_map string,int min_cost;int start_h mahattan(start,pos_map);open_list.push(Node(start,0,start_h));min_cost[start] 0;while(!open_list.empty()){Node cur open_list.top();open_list.pop();string state cur.state;if(state TARGET) return cur.g;//非最优路径则跳过if(min_cost[state] cur.g) continue;//找出0的位置 int pos state.find(0);int x pos % 3;int y pos / 3;for(int i 0;i 4;i){int tx x dx[i];int ty y dy[i];//越界 if(tx 0 || tx 3 || ty 0 || ty 3) continue;//0的新坐标 int new_pos tx ty * 3;string new_state state;swap(new_state[pos],new_state[new_pos]);int new_g cur.g 1;//未曾入队或有更优解 if(min_cost.find(new_state) min_cost.end() || new_g min_cost[new_state]){min_cost[new_state] new_g;int new_h mahattan(new_state,pos_map);open_list.push(Node(new_state,new_g,new_h));} }}
}int main(){ios::sync_with_stdio(0);cin.tie(0);string start;cin start;cout A_star(start) endl;return 0;
}
