美工素材网站,舆情系统,自己做局域网站,高档网站建设公司算法进阶-搜索 题目描述#xff1a;给定一张N个点M条边的有向无环图#xff0c;分别统计从每个点除法能够到达的点的数量 **数据规模#xff1a;**1 n 3e4 **分析#xff1a;**这里我们可以使用拓扑排序根据入边对所有点进行排序#xff0c;排序后我们按照逆序给定一张N个点M条边的有向无环图分别统计从每个点除法能够到达的点的数量 **数据规模**1 n 3e4 **分析**这里我们可以使用拓扑排序根据入边对所有点进行排序排序后我们按照逆序结合状态压缩将相连接的点存入bitset中(使用或操作)最后我们从1开始到n返回二进制中1的个数即是可到达点的个数。这里只要是这两个点相连接后一个点就和前一个点的所有位置进行或运算 题解: 见分析 TIPSjava中集成有BitSetset是将对应位置设为真cardinality返回当前二进制中1的个数 时间复杂度O(N*M) #includeiostream
#includebitset
#includecstring
#includequeue
using namespace std;const int N 3e4 10;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], seq[N];bitsetN f[N];void add(int u, int v){e[idx] v, ne[idx] h[u], h[u] idx;
}void topsort(){queueint q;for(int i 1; i n; i){if(!d[i]) q.push(i);}int k 0;while(q.size()){int t q.front();q.pop();seq[k] t;for(int i h[t]; ~i; i ne[i]){int j e[i];if(!--d[j]) q.push(j);}}
}
int main(){cin n m;memset(h, -1, sizeof h);for(int i 0; i m; i){int u, v;cin u v;add(u, v);d[v];}topsort();for(int i n - 1; ~i; i--){int j seq[i];f[j][j] 1;for(int p h[j]; ~p; p ne[p]) f[j] | f[e[p]];}for(int i 1; i n; i) cout f[i].count() endl;return 0;
}
import java.util.*;public class Main {public static void main(String[] args) {new Main().run();}final int N (int) (3e4 10);int[] h new int[N], e new int[N], next new int[N];int idx 0;int[] d new int[N], seq new int[N];int n, m;BitSet[] sets new BitSet[N];void topSort(){QueueInteger q new ArrayDeque();int idx 0;for(int i 1; i n; i) if(d[i] 0) q.add(i);while(!q.isEmpty()){int u q.poll();seq[idx] u;for(int i h[u]; i ! -1; i next[i]){int j e[i];if(--d[j] 0) q.add(j);}}}void add(int u, int v){e[idx] v;next[idx] h[u];h[u] idx;}void run(){Scanner sc new Scanner(System.in);n sc.nextInt();m sc.nextInt();for (int i 0; i n; i) sets[i] new BitSet();Arrays.fill(h, -1);for(int i 0; i m; i){int u sc.nextInt(), v sc.nextInt();add(u, v);d[v];}topSort();for(int i n - 1; i 0; i--){int j seq[i];sets[j].set(j);for(int p h[j]; p ! -1; p next[p]){int edge e[p];sets[j].or(sets[edge]);}}for(int i 1; i n; i) System.out.println(sets[i].cardinality());sc.close();}
}题目描述给定n个商品和对应商品的重量。我们想将商品放入包裹包裹可承载的重量之和不能超过w。现在我们想知道最少需要多少包裹可以使全部包裹放入 **数据规模**1 n 18 **分析**这里要递归来扫描整个状态空间其中有两个变量当前商品的编号以及包裹的编号。我们想让整棵树的分支尽可能少因此在上面要尽量放大的商品。 题解: 见分析 TIPS无 时间复杂度O(2^n) #includeiostream
#includealgorithmusing namespace std;const int N 20;
int n, m;
int cat[N], sum[N];
int ans N;/**** param u 猫的编号* param k 缆车的编号*/
void dfs(int u, int k){if(k ans) return;//剪枝-若当前缆车编号大于或等于ans则跳出if(u n){//边界条件ans k;return;}//1.若当前猫的重量可以放入for(int i 0; i k; i){if(cat[u] sum[i] m){sum[i] cat[u];dfs(u 1, k);sum[i] - cat[u];}}//2.放入新的缆车sum[k] cat[u];dfs(u 1, k 1);sum[k] 0;
}
int main(){cin n m;for(int i 0; i n; i){cin cat[i];}sort(cat, cat n);reverse(cat, cat n);dfs(0, 0);cout ans endl;return 0;
}import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 20;int n, m;Integer[] cat new Integer[N];int[] sum new int[N];int ans N;/*** 递归* param u 当前猫* param k 当前缆车*/void dfs(int u, int k){//剪枝if(k ans) return;//边界条件if(u n){ans k;return;}//1.若当前猫可以放入for(int i 0; i k; i){if(cat[u] sum[i] m){sum[i] cat[u];dfs(u 1, k);sum[i] - cat[u];}}//2.放入新的缆车sum[k] cat[u];dfs(u 1, k 1);sum[k] 0;}void run(){Scanner sc new Scanner(System.in);n sc.nextInt();m sc.nextInt();for(int i 0; i n; i) cat[i] sc.nextInt();Arrays.sort(cat, 0, n, (a, b) - b - a);dfs(0, 0);System.out.println(ans);}
}题目描述给出数独的所有状态请将它填满。 **数据规模**n 9 **分析**这里数据量很大要预处理不同数二进制下1的个数和对应二进制次幂的指数这样我们就可以在O(1)时间内求得对应值。我们进行搜索时优先从少的情况开始搜索这样就大大减少了搜索范围。 题解: 对row、col和cell进行初始化将对应二进制所有的位都置为1代表未选状态。枚举字符串的所有位置看有多少格子要填以及将对应二进制位的数字置为1.这里需要注意字符串中是19二进制对应的是08要转换进行递归搜索我们枚举所有位置看哪个位置可选项最少即填的最多从这里开始搜索搜索时每次选一个可选项选后要对二进制状态以及字符数组进行修改选后向下搜索。最后进行回溯将状态还原。边界条件是: cnt 0即全部填满即返回。否则返回false TIPS需要使用到lowbit运算、状态压缩、递归优化 时间复杂度未知 #includeiostreamusing namespace std;
const int N 9;int ones[1 N], map[1 N];//ones记录一个状态值中1的个数map记录logn为多少
int row[N], col[N], cell[N][N];
char str[100];
/*** 获取最后一个1* param x* return*/
inline int lowbit(int x){return x -x;
}void init(){for(int i 0; i N; i) row[i] col[i] (1 N) - 1;//初始状态时全为111111111for(int i 0; i 3; i)for(int j 0; j 3; j) cell[i][j] (1 N) - 1;//同理
}/*** 可选方案的交集* param x* param y* return*/
inline int get(int x, int y){return row[x] row[y] cell[x / 3][y / 3];
}bool dfs(int cnt){if(!cnt) return true;//找出可选方案数最少的空格int minv 10;int x, y;for(int i 0; i N; i)for(int j 0; j N; j)if(str[i * N j] .){int t ones[get(i, j)];//寻找合法数字的个数if(t minv){//寻找状态空位中最少的状态minv t;x i, y j;//记录空位最少的下标}}for(int i get(x, y); i; i - lowbit(i)){int t map[lowbit(i)];//修改状态row[x] - 1 t;col[y] - 1 t;cell[x / 3][y / 3] - 1 t;str[x * N y] 1 t;if(dfs(cnt - 1)) return true;row[x] 1 t;col[y] 1 t;cell[x / 3][y / 3] 1 t;str[x * N y] .;}return false;
}
int main(){for(int i 0; i N; i) map[1 i] i;//求lognfor(int i 0; i 1 N; i){int s 0;for(int j i; j; j - lowbit(j)) s;ones[i] s;}while(cin str, str[0] ! e){init();int cnt 0;for(int i 0, k 0; i N; i){for(int j 0; j N; j, k){if(str[k] ! .){int t str[k] - 1;row[i] - 1 t;col[j] - 1 t;cell[i / 3][j / 3] - 1 t;}else cnt;}}dfs(cnt);}cout str endl;return 0;
}import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 9;//ones记录对应二进制中1的个数map记录对应数的对数int[] ones new int[1 N], map new int[1 N];int[] row new int[N], col new int[N];int[][] cell new int[3][3];char[] str;/*** 取出最低位的1以及后续数* param x* return*/int lowbit(int x){return x -x;}/*** 初始化row、col和cell*/void init(){for(int i 0; i N; i) row[i] col[i] (1 N) - 1;//对应位全位1for(int i 0; i 3; i)for(int j 0; j 3; j) cell[i][j] (1 N) - 1;}/*** 求可选方案的交集* param x* param y* return*/int get(int x, int y){return row[x] col[y] cell[x / 3][y / 3];}boolean dfs(int cnt){//边界条件if(cnt 0) return true;//找出可选方案数最少的空格int min 10;int x 0, y 0;//扫描对应位置看是否位空格for(int i 0; i N; i){for(int j 0; j N; j){if(str[i * N j] .){int t ones[get(i, j)];if(t min){min t;x i;y j;}}}}//每次拿掉一种可能for(int i get(x, y); i 0; i - lowbit(i)){int t map[lowbit(i)];//求对应的二进制的对数//修改状态row[x] - 1 t;col[y] - 1 t;//0~8转化位1~9cell[x / 3][y / 3] - 1 t;str[x * N y] (char)(1 t);if(dfs(cnt - 1)) return true;//还原row[x] 1 t;col[y] 1 t;cell[x / 3][y / 3] 1 t;str[x * N y] .;}return false;}void run(){for(int i 0; i N; i) map[1 i] i;//预处理for(int i 0; i 1 N; i){int s 0;for(int j i; j 0; j - lowbit(j)) s;ones[i] s;}Scanner sc new Scanner(System.in);while(true){String s sc.next();if(s.equals(end)) break;str s.toCharArray();init();int cnt 0;//记录有多少格子要填for(int i 0, k 0; i N; i){for(int j 0; j N; j, k){//将对应二进制变位0if(str[k] ! .){//将1~9转化为0~8int t str[k] - 1;row[i] - 1 t;col[j] - 1 t;cell[i / 3][j / 3] - 1 t;}else cnt;}}dfs(cnt);for(int i 0; i str.length; i) System.out.print(str[i]);System.out.println();}sc.close();}
}题目描述给出数独的所有状态请将它填满。 **数据规模**n 16 分析 搜索顺序:每次找到一个空格枚举空格选择哪个字母然后往下递归。边界条件所有空格都填完。状态的存储state[x] [y]表示x行y列这个格子可以填哪些数(015),我们用16位二进制来表示所有状态为02^16-1 优化 对于每个空格如果不能填任何一个字母无解如果只能填一个字母那么直接填上。对于每一行如果某个字母不能出现在任何一个位置无解如果某个字母只有一个位置可以填则直接填上对于每一列同理对于每一个16宫格类似每次选择空格时选择备选方案最少得格子来填。 题解: 对row、col和cell进行初始化将对应二进制所有的位都置为1代表未选状态。枚举字符串的所有位置看有多少格子要填以及将对应二进制位的数字置为1.这里需要注意字符串中是19二进制对应的是08要转换进行递归搜索我们枚举所有位置看哪个位置可选项最少即填的最多从这里开始搜索搜索时每次选一个可选项选后要对二进制状态以及字符数组进行修改选后向下搜索。最后进行回溯将状态还原。边界条件是: cnt 0即全部填满即返回。否则返回false TIPS需要使用到lowbit运算、状态压缩、递归优化 时间复杂度未知 #includeiostream
#includecstringusing namespace std;
const int N 16, M N * N 1;
int ones[1 N], log_arr[1 N];
int state[N][N];
char str[N][N 1];
int bstate[M][N][N], bstate2[M][N][N];
char bstr[M][N][N 1];/*** lowbit运算取出二进制下最低位的1* param x* return*/
inline int lowbit(int x){return x -x;
}/*** 将字符串数组和state的状态进行变更* param x* param y* param c*/
void draw(int x, int y, int c){str[x][y] c A;//更改字符串数组为对应字母for(int i 0; i N; i){state[x][i] ~(1 c);//将二进制对应位置置为0表示已选state[i][y] ~(1 c);}//将16宫格对应位置置为0表示已选int sx x / 4 * 4, sy y / 4 * 4;for(int i 0; i 4; i)for(int j 0; j 4; j)state[sx i][sy j] ~(1 c);//表示该位置选了cstate[x][y] 1 c;
}bool dfs(int cnt){//边界条件当cnt 0即全部找到返回if(!cnt) return true;//备份cnt、state、str后续失败后还原int kcnt cnt;memcpy(bstate[kcnt], state, sizeof state);memcpy(bstr[kcnt], str, sizeof str);//1.剪枝对于每个空格若不能填任何数则返回false若只能填一个数就填上for(int i 0; i N; i){for(int j 0; j N; j){if(str[i][j] -){//若可以填数//获取当前状态即可选项int t state[i][j];//若都不可选即全为0还原后直接返回falseif(!t){memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;}//若只有一个可选就填上if(ones[t] 1){draw(i, j, log_arr[t]);cnt--;}}}}//剪枝2.对于每行若某个字母不能出现在任何一个位置则返回false若某个字母只有一个位置可填则直接填for(int i 0; i N; i){//这里sor填的是所有备选方案的并集sand是所有备选方案就交集用来找某个字母只有一个位置可填int sor 0, sand (1 N) - 1;int drawn 0;//表示已经填上的字母for(int j 0; j N; j){int s state[i][j];sand ~(sor s);//将不符合要求的删掉sor | s;//求备选方案的并if(str[i][j] ! -) drawn | s;//将当前位置信息保存在drawn中}//该改行不能选完所有数就还原结束if(sor ! (1 N) - 1){memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;}//枚举该数字看有哪个位置可填for(int j sand; j; j - lowbit(j)){int t lowbit(j);//若正好当前数未填过if(!(drawn t)){for(int k 0; k N; k){//若该位置可填就填上if(state[i][k] t){draw(i, k, log_arr[t]);cnt--;break;}}}}}//对于每一列同理for(int i 0; i N; i){int sor 0, sand (1 N) - 1;int drawn 0;for(int j 0; j N; j){int s state[j][i];sand ~(sor s);sor | s;if(str[j][i] ! -) drawn | s;}if(sor ! (1 N) - 1){memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;}for(int j sand; j; j - lowbit(j)){int t lowbit(j);if(!(drawn t)){for(int k 0; k N; k){if(state[k][i] t){draw(k, i, log_arr[t]);cnt--;break;}}}}}//对于每个16宫格for(int i 0; i N; i){int sor 0, sand (1 N) - 1;int drawn 0;for(int j 0; j N; j){int sx i / 4 * 4, sy i % 4 * 4;int dx j / 4, dy j % 4;int s state[sx dx][sy dy];sand ~(sor s);sor | s;if(str[sx dx][sy dy] ! -) drawn | state[sx dx][sy dy];}if(sor ! (1 N) - 1){memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;}for(int j sand; j; j - lowbit(j)){int t lowbit(j);if(!(drawn t)){for(int k 0; k N; k){int sx i / 4 * 4, sy i % 4 * 4;int dx k / 4, dy k % 4;if(state[sx dx][sy dy] t){draw(sx dx, sy dy, log_arr[t]);cnt--;break;}}}}}//若都填满了if(!cnt) return true;//每次选最少得格子来填int x, y, s 100;for(int i 0; i N; i){for(int j 0; j N; j){int t state[i][j];if(str[i][j] - ones[t] s){s ones[t];x i, y j;}}}//这里先备份memcpy(bstate2[kcnt], state, sizeof state);for(int i state[x][y]; i; i - lowbit(i)){memcpy(state, bstate2[kcnt], sizeof state);draw(x, y, log_arr[lowbit(i)]);if(dfs(cnt - 1)) return true;}//还原memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;
}int main(){for(int i 0; i N; i) log_arr[1 i] i;//初始化log数组存对应数的对数for(int i 0; i 1 N; i)for(int j i; j; j - lowbit(j)) ones[i];//求所有数中1的个数/*** 输入字符串初始化state数组状态全为1即为都可选*/while(cin str[0]){for(int i 1; i N; i) cin str[i];for(int i 0; i N; i)for(int j 0; j N; j)state[i][j] (1 N) - 1;int cnt 0;//有多少数要填//根据字母对状态数组将进行更改for(int i 0; i N; i){for(int j 0; j N; j)if(str[i][j] ! -) draw(i, j, str[i][j] - A);else cnt;}//递归求答案dfs(cnt);//输出for(int i 0; i N; i) cout str[i] endl;puts();}return 0;
}
#includeiostream
#includecstringusing namespace std;
const int N 16, M N * N 1;
int ones[1 N], log_arr[1 N];
int state[N][N];
char str[N][N 1];
int bstate[M][N][N], bstate2[M][N][N];
char bstr[M][N][N 1];/*** lowbit运算取出二进制下最低位的1* param x* return*/
inline int lowbit(int x){return x -x;
}/*** 将字符串数组和state的状态进行变更* param x* param y* param c*/
void draw(int x, int y, int c){str[x][y] c A;//更改字符串数组为对应字母for(int i 0; i N; i){state[x][i] ~(1 c);//将二进制对应位置置为0表示已选state[i][y] ~(1 c);}//将16宫格对应位置置为0表示已选int sx x / 4 * 4, sy y / 4 * 4;for(int i 0; i 4; i)for(int j 0; j 4; j)state[sx i][sy j] ~(1 c);//表示该位置选了cstate[x][y] 1 c;
}bool dfs(int cnt){//边界条件当cnt 0即全部找到返回if(!cnt) return true;//备份cnt、state、str后续失败后还原int kcnt cnt;memcpy(bstate[kcnt], state, sizeof state);memcpy(bstr[kcnt], str, sizeof str);//1.剪枝对于每个空格若不能填任何数则返回false若只能填一个数就填上for(int i 0; i N; i){for(int j 0; j N; j){if(str[i][j] -){//若可以填数//获取当前状态即可选项int t state[i][j];//若都不可选即全为0还原后直接返回falseif(!t){memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;}//若只有一个可选就填上if(ones[t] 1){draw(i, j, log_arr[t]);cnt--;}}}}//剪枝2.对于每行若某个字母不能出现在任何一个位置则返回false若某个字母只有一个位置可填则直接填for(int i 0; i N; i){//这里sor填的是所有备选方案的并集sand是所有备选方案就交集用来找某个字母只有一个位置可填int sor 0, sand (1 N) - 1;int drawn 0;//表示已经填上的字母for(int j 0; j N; j){int s state[i][j];sand ~(sor s);//将不符合要求的删掉sor | s;//求备选方案的并if(str[i][j] ! -) drawn | s;//将当前位置信息保存在drawn中}//该改行不能选完所有数就还原结束if(sor ! (1 N) - 1){memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;}//枚举该数字看有哪个位置可填for(int j sand; j; j - lowbit(j)){int t lowbit(j);//若正好当前数未填过if(!(drawn t)){for(int k 0; k N; k){//若该位置可填就填上if(state[i][k] t){draw(i, k, log_arr[t]);cnt--;break;}}}}}//对于每一列同理for(int i 0; i N; i){int sor 0, sand (1 N) - 1;int drawn 0;for(int j 0; j N; j){int s state[j][i];sand ~(sor s);sor | s;if(str[j][i] ! -) drawn | s;}if(sor ! (1 N) - 1){memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;}for(int j sand; j; j - lowbit(j)){int t lowbit(j);if(!(drawn t)){for(int k 0; k N; k){if(state[k][i] t){draw(k, i, log_arr[t]);cnt--;break;}}}}}//对于每个16宫格for(int i 0; i N; i){int sor 0, sand (1 N) - 1;int drawn 0;for(int j 0; j N; j){int sx i / 4 * 4, sy i % 4 * 4;int dx j / 4, dy j % 4;int s state[sx dx][sy dy];sand ~(sor s);sor | s;if(str[sx dx][sy dy] ! -) drawn | state[sx dx][sy dy];}if(sor ! (1 N) - 1){memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;}for(int j sand; j; j - lowbit(j)){int t lowbit(j);if(!(drawn t)){for(int k 0; k N; k){int sx i / 4 * 4, sy i % 4 * 4;int dx k / 4, dy k % 4;if(state[sx dx][sy dy] t){draw(sx dx, sy dy, log_arr[t]);cnt--;break;}}}}}//若都填满了if(!cnt) return true;//每次选最少得格子来填int x, y, s 100;for(int i 0; i N; i){for(int j 0; j N; j){int t state[i][j];if(str[i][j] - ones[t] s){s ones[t];x i, y j;}}}//这里先备份memcpy(bstate2[kcnt], state, sizeof state);for(int i state[x][y]; i; i - lowbit(i)){memcpy(state, bstate2[kcnt], sizeof state);draw(x, y, log_arr[lowbit(i)]);if(dfs(cnt - 1)) return true;}//还原memcpy(state, bstate[kcnt], sizeof state);memcpy(str, bstr[kcnt], sizeof str);return false;
}int main(){for(int i 0; i N; i) log_arr[1 i] i;//初始化log数组存对应数的对数for(int i 0; i 1 N; i)for(int j i; j; j - lowbit(j)) ones[i];//求所有数中1的个数/*** 输入字符串初始化state数组状态全为1即为都可选*/while(cin str[0]){for(int i 1; i N; i) cin str[i];for(int i 0; i N; i)for(int j 0; j N; j)state[i][j] (1 N) - 1;int cnt 0;//有多少数要填//根据字母对状态数组将进行更改for(int i 0; i N; i){for(int j 0; j N; j)if(str[i][j] ! -) draw(i, j, str[i][j] - A);else cnt;}//递归求答案dfs(cnt);//输出for(int i 0; i N; i) cout str[i] endl;puts();}return 0;
} import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Main().run();}final int N 16, M N * N 1;int[] ones new int[1 N], log new int[1 N];int[][] state new int[N][N];char[][] str new char[N][N 1];int[][][] bstate new int[M][N][N], bstate2 new int[M][N][N];char[][][] bstr new char[M][N][N 1];int lowbit(int x){return x -x;}void draw(int x, int y, int c){str[x][y] (char)(c A);for(int i 0; i N; i){state[x][i] ~(1 c);state[i][y] ~(1 c);}int sx x / 4 * 4, sy y / 4 * 4;for(int i 0; i 4; i)for(int j 0; j 4; j)state[sx i][sy j] ~(1 c);state[x][y] 1 c;}boolean dfs(int cnt){if(cnt 0) return true;int kcnt cnt;for(int i 0; i N; i) {System.arraycopy(str[i], 0, bstr[kcnt][i], 0, N);System.arraycopy(state[i], 0, bstate[kcnt][i],0, N);}for(int i 0; i N; i){for(int j 0; j N; j){if(str[i][j] -){int t state[i][j];if(t 0){for(int k 0; k N; k) {System.arraycopy(bstr[kcnt][k], 0, str[k], 0, N);System.arraycopy(bstate[kcnt][k], 0, state[k],0, N);}return false;}if(ones[t] 1){draw(i, j, log[t]);cnt--;}}}}//行for(int i 0; i N; i){int sor 0, sand (1 N) - 1;int drawn 0;for(int j 0; j N; j){int s state[i][j];sand ~(sor s);sor | s;if(str[i][j] ! -) drawn | s;}if(sor ! (1 N) - 1){for(int k 0; k N; k){System.arraycopy(bstr[kcnt][k], 0, str[k], 0, N);System.arraycopy(bstate[kcnt][k], 0, state[k],0, N);}return false;}for(int j sand; j 0; j- lowbit(j)){int t lowbit(j);if((drawn t) 0){for(int k 0; k N; k){if((state[i][k] t) 0){draw(i, k, log[t]);cnt--;break;}}}}}//列for(int i 0; i N; i){int sor 0, sand (1 N) - 1;int drawn 0;for(int j 0; j N; j){int s state[j][i];sand ~(sor s);sor | s;if(str[j][i] ! -) drawn | s;}if(sor ! (1 N) - 1){for(int k 0; k N; k){System.arraycopy(bstr[kcnt][k], 0, str[k], 0, N);System.arraycopy(bstate[kcnt][k], 0, state[k],0, N);}return false;}for(int j sand; j 0; j- lowbit(j)){int t lowbit(j);if((drawn t) 0){for(int k 0; k N; k){if((state[k][i] t) 0){draw(k, i, log[t]);cnt--;break;}}}}}//16宫格for(int i 0; i N; i){int sor 0, sand (1 N) - 1;int drawn 0;for(int j 0; j N; j){int sx i / 4 * 4, sy i % 4 * 4;int dx j / 4, dy j % 4;int s state[sx dx][sy dy];sand ~(sor s);sor | s;if(str[sx dx][sy dy] ! -) drawn | state[sx dx][sy dy];}if(sor ! (1 N) - 1){for(int k 0; k N; k){System.arraycopy(bstr[kcnt][k], 0, str[k], 0, N);System.arraycopy(bstate[kcnt][k], 0, state[k],0, N);}return false;}for(int j sand; j 0; j - lowbit(j)){int t lowbit(j);if((drawn t) 0){for(int k 0; k N; k){int sx i / 4 * 4, sy i % 4 * 4;int dx k / 4, dy k % 4;if((state[sx dx][sy dy] t) 0){draw(sx dx, sy dy, log[t]);cnt--;break;}}}}}if(cnt 0) return true;int x 0, y 0, s 100;for(int i 0; i N; i){for(int j 0; j N; j){int t state[i][j];if(str[i][j] - ones[t] s){s ones[t];x i;y j;}}}for(int k 0; k N; k){System.arraycopy(state[k], 0, bstate2[kcnt][k], 0, N);}for(int i state[x][y]; i 0; i - lowbit(i)){for(int k 0; k N; k){System.arraycopy(bstate2[kcnt][k], 0, state[k], 0, N);}draw(x, y, log[lowbit(i)]);if(dfs(cnt - 1)) return true;}for(int i 0; i N; i){System.arraycopy(bstate[kcnt][i], 0, state[i], 0, N);System.arraycopy(bstr[kcnt][i], 0, str[i], 0, N);}return false;}StringTokenizer stringTokenizer;BufferedReader bufferedReader new BufferedReader(new InputStreamReader(System.in));String next(){while(stringTokenizer null || !stringTokenizer.hasMoreElements()){try {stringTokenizer new StringTokenizer(bufferedReader.readLine());} catch (IOException e) {e.printStackTrace();}}return stringTokenizer.nextToken();}void run(){for(int i 0; i N; i) log[1 i] i;for(int i 0; i N; i)for(int j i; j 0; j - lowbit(j)) ones[i];PrintWriter out new PrintWriter(System.out);while(true){for(int i 0; i N; i){char[] line next().toCharArray();for(int j 0; j N; j){str[i][j] line[j];}}for(int i 0; i N; i){for(int j 0; j N; j)state[i][j] (1 N) - 1;}int cnt 0;for(int i 0; i N; i){for(int j 0; j N; j){if(str[i][j] ! -) draw(i, j, str[i][j] - A);else cnt;}}dfs(cnt);for(int i 0; i N; i){for(int j 0; j N; j) out.print(str[i][j]);out.println();}out.println();out.flush();if(!stringTokenizer.hasMoreTokens()) break;}}
} 题目描述若序列满足以下要求x[1] 1, x[m] n ,x[1] x[2] … x[m - 1] x[m],对于每个k(1 k m)都存在两个整数i和j(1 i, j k - 1, i和j可相等)使得x[k] x[i] x[j]则被称为加成序列。现在给定一个整数n找出符合上述条件的长度m最小的加成序列。 **数据规模**1 n 100 **分析**这里要找出符合上述条件的长度位m最小的加成序列。这里我们可以采用迭代加深的思想进行搜索。 优化 迭代加深进行深度搜索我们用path存储序列去重避免重复搜索 题解: 见分析 TIPS 时间复杂度O(2^20) #includeiostreamusing namespace std;const int N 110;
int n;
int path[N];bool dfs(int u, int depth){if(u depth) return path[u - 1] n;bool st[N] {false};for(int i u - 1; i 0; i--){for(int j i; j 0; j--){int s path[i] path[j];//1.保证递增. 2.保证小于或等于n. 3.保证未选用于去重if(s path[u - 1] s n !st[s]){st[s] true;path[u] s;if(dfs(u 1, depth)) return true;}}}return false;
}
int main(){while(cin n, n){int depth 1;path[0] 1;while(!dfs(1, depth)) depth;for(int i 0; i depth; i) cout path[i] ;cout endl;}return 0;
}import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 110;int n;int[] path new int[N];/*** 搜索* param u 存储当前下标* param depth 要搜索的深度* return*/boolean dfs(int u, int depth){if(u depth) return path[u - 1] n;boolean[] st new boolean[N];for(int i u - 1; i 0; i--){for(int j i; j 0; j--){int s path[i] path[j];if(s path[u - 1] s n !st[s]){st[s] true;path[u] s;if(dfs(u 1, depth)) return true;}}}return false;}void run(){Scanner sc new Scanner(System.in);while(true){n sc.nextInt();if(n 0) break;int depth 1;path[0] 1;while(!dfs(1, depth)) depth;for(int i 0; i depth; i) System.out.print(path[i] );System.out.println();}sc.close();}
} 题目描述有N个物品其中第i个的重量是g[i]。一次可以拿的物品重量不超过w。现在想知道在不超过w的情况下一次能搬动的最大重量是多少 **数据规模**1 n 46 1 w,g[i] 2^31 - 1 **分析**这里可以采用双向dfs搜索将时间复杂度大幅度降低体现了以空间换时间的思想。 先搜索前N/2个物品可以凑出来的所有重量存到数组当中去。对所有重量排序判重。再搜索后一半物品可以凑出来的重量。假设当前的重量是x则可以在预处理出的所有重量中二分出一个y使得 x y w,且x y最大。 优化 从大到小枚举所有质量。均衡两次搜索的时间。 题解: 见分析 TIPS 时间复杂度O(2^24) #includeiostream
#includealgorithmusing namespace std;
typedef long long LL;
const int N 46;int n, m, k;
LL g[N];
LL weight[1 24], cnt;
LL ans 0;
/**** param u 当前层* param s 当前重量*/
void dfs_1(int u, int s){if(u k){weight[cnt] s;return;}if(s g[u] m) dfs_1(u 1, s g[u]);dfs_1(u 1, s);
}void dfs_2(int u, int s){if(u n){int l 0, r cnt - 1;while(l r){int mid l r 1 1;if(weight[mid] s m) l mid;else r mid - 1;}if(weight[l] s m) ans max(ans, weight[l] s);return;}if(s g[u] m) dfs_2(u 1, s g[u]);dfs_2(u 1, s);
}int main(){cin m n;for(int i 0; i n; i) cin g[i];sort(g, g n, greaterint());k n / 2 2;dfs_1(0, 0);sort(weight, weight cnt);cnt unique(weight, weight cnt) - weight;dfs_2(k, 0);cout ans endl;return 0;
}import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeSet;public class Main {public static void main(String[] args) {new Main().run();}final int N 46;int n, k, m; //分别代表的个数搜索的分割点和可移动的最大质量Integer[] g new Integer[N];//存放所有礼物的质量int[] weight new int[1 24];//存放枚举的质量之和int cnt 0;//质量之和的下标long ans 0;//当前合法最大质量TreeSetInteger set new TreeSet();//有序集合用于存放去重之后的质量之和按升序排序/*** 第一次搜索* param u 当前位置* param s 当前质量之和*/void dfs1(int u, int s){//边界条件若下标等于分界点就将当前s存入weight中并返回if(u k) {weight[cnt] s;return;}//分割条件:优先选当前数若结果之和小于mif((long) g[u] s m) dfs1(u 1, g[u] s);//不选当前数dfs1(u 1, s);}void dfs2(int u, int s){//边界条件: 若当前下标位结尾就在有序集合中找一个最大的小于或等于目标数m - 当前数s的数并用该数更新ans最后返回if(u n){int t set.floor(m - s);ans Math.max(ans, s t);return;}//分割:选当前数或不选优先选if((long) s g[u] m) dfs2(u 1, s g[u]);dfs2(u 1, s);}void run(){Scanner sc new Scanner(System.in);m sc.nextInt();n sc.nextInt();for (int i 0; i n; i) {g[i] sc.nextInt();}sc.close();Arrays.sort(g, 0, n, (a, b) - b - a);k n / 2 1;dfs1(0, 0);for(int i 0; i cnt; i) set.add(weight[i]);dfs2(k, 0);System.out.println(ans);}
}题目描述立体推箱子我们给定箱子的初始位置以及初始状态我们想让箱子到目标位置。箱子可以往前后左右滚动每次滚动只能转动90度现在想知道从起始位置到终止位置最少需要多少步 **数据规模**3 N, M 500 **分析**从起点想知道到终点最少需要多少步可以用宽搜来做。因为每个位置对应有三种状态竖直、横着、竖着。三种状态三种状态。这类题目对于状态的转移很重要。我们将状态存入Node中有三个属性x、y、lie表示当前长方体的位置以及摆放的状态。dist中存放的是不同状态离初始位置的距离。 **优化**无 题解: 见分析 TIPS无 时间复杂度O(N^2 * 3) #includeiostream
#includecstring
#includequeue
#includealgorithmusing namespace std;
const int N 510;
struct State{int x, y, lie;
};
char g[N][N];
int dis[N][N][3];
int f[3][4][3] {{{-2, 0, 2}, {1, 0, 2}, {0, -2, 1}, {0, 1, 1}},{{-1, 0, 1}, {1, 0, 1}, {0, -1, 0}, {0, 2, 0}},{{-1, 0, 0}, {2, 0, 0}, {0, -1, 2}, {0, 1, 2}}
};
int n, m;bool check(int x, int y){if(x 0 || x n || y 0 || y m) return false;return g[x][y] ! #;
}
int bfs(State start, State end){memset(dis, -1, sizeof dis);dis[start.x][start.y][start.lie] 0;queueState queue;queue.push(start);while(queue.size()){auto t queue.front();queue.pop();for(int i 0; i 4; i){State next {t.x f[t.lie][i][0], t.y f[t.lie][i][1], f[t.lie][i][2]};int x next.x, y next.y;if(!check(x, y)) continue;if(next.lie 0 g[x][y] E) continue;if(next.lie 1 !check(x, y 1)) continue;if(next.lie 2 !check(x 1, y)) continue;if(dis[x][y][next.lie] -1){dis[x][y][next.lie] dis[t.x][t.y][t.lie] 1;queue.push(next);}}}return dis[end.x][end.y][end.lie];
}
int main(){while(cin n m, n || m){for(int i 0; i n; i) cin g[i];State start {-1}, end;for(int i 0; i n; i){for(int j 0; j m; j){if(g[i][j] X start.x -1){if(g[i][j 1] X) start {i, j, 1};else if(g[i 1][j] X) start {i, j, 2};else start {i, j, 0};}else if(g[i][j] O) end {i, j, 0};}}int ans bfs(start, end);if(ans -1) puts(Impossible);else printf(%d\n, ans);}return 0;}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;public class Main {public static void main(String[] args) {new Main().run();}final int N 510;/*** x、y分别表示横坐标和纵坐标lie表示长方体的拜访状态。0-直立、1-横着、2-竖着*/class Node{int x, y, lie;public Node(int x, int y, int lie) {this.x x;this.y y;this.lie lie;}Overridepublic String toString() {return Node{ x x , y y , lie lie };}}int[][][] f {{{-2, 0, 2}, {1, 0, 2}, {0, -2, 1}, {0, 1, 1}},{{-1, 0, 1}, {1, 0, 1}, {0, -1, 0}, {0, 2, 0}},{{-1, 0, 0}, {2, 0, 0}, {0, -1, 2}, {0, 1, 2}}};char[][] g new char[N][N];//存地图int[][][] dist new int[N][N][3];//存放当前状态与原点的距离初始为-1代表未走过int n, m;boolean check(int x, int y){if(x 0 || x n || y 0 || y m) return false;return g[x][y] ! #;}/*** 广度优先搜索* param start* param end* return*/int bfs(Node start, Node end){for (int i 0; i n; i) {for(int j 0; j m; j){Arrays.fill(dist[i][j], -1);}}dist[start.x][start.y][start.lie] 0;QueueNode queue new ArrayDeque();queue.offer(start);while(!queue.isEmpty()){Node cur queue.poll();for (int i 0; i 4; i) {Node next new Node(cur.x f[cur.lie][i][0], cur.y f[cur.lie][i][1], f[cur.lie][i][2]);int x next.x, y next.y;if(!check(x, y)) continue;if(next.lie 0 g[x][y] E) continue;//立着if(next.lie 1 !check(x, y 1)) continue;//横着if(next.lie 2 !check(x 1, y)) continue;//竖着if(dist[x][y][next.lie] -1){//未访问dist[x][y][next.lie] dist[cur.x][cur.y][cur.lie] 1;//步数1queue.offer(next);}}}return dist[end.x][end.y][end.lie];}StringTokenizer stringTokenizer;BufferedReader bufferedReader new BufferedReader(new InputStreamReader(System.in));String next(){while(stringTokenizer null || !stringTokenizer.hasMoreTokens()){try {stringTokenizer new StringTokenizer(bufferedReader.readLine());} catch (IOException e) {e.printStackTrace();}}return stringTokenizer.nextToken();}int nextInt(){return Integer.parseInt(next());}void run(){while(true){n nextInt();m nextInt();if(n 0 m 0) break;for(int i 0; i n; i) {g[i] next().toCharArray();}Node start new Node(-1, -1, -1), end new Node(-1, -1, -1);for(int i 0; i n; i){for(int j 0; j m; j){if(g[i][j] X start.x -1){//这里要保证是第一个if(g[i][j 1] X){start new Node(i, j, 1);}else if(g[i 1][j] X){start new Node(i, j, 2);}else{start new Node(i, j, 0);}}else if(g[i][j] O){end new Node(i, j, 0);}}}int ans bfs(start, end);if(ans -1){System.out.println(Impossible);}else System.out.println(ans);}}
}题目描述给定一个01矩阵定义曼哈顿距离-即两点的纵坐标之差与横坐标只差的和 d i s t ( A [ i ] [ j ] , A [ k ] [ l ] ) ∣ i − k ∣ [ j − l ] dist(A[i][j], A[k][l]) |i - k| [j - l] dist(A[i][j],A[k][l])∣i−k∣[j−l] 输出一个N行M列的整数矩阵表示当前位置到最近1的距离 B [ i ] [ j ] m i n 1 ≤ x ≤ N , 1 ≤ y ≤ M , A [ x ] [ y ] 1 d i s t ( A [ i ] [ j ] , A [ x ] [ y ] ) B[i][j] min_{1 \leq x \leq N, 1\leq y \leq M, A[x][y] 1} dist(A[i][j], A[x][y]) B[i][j]min1≤x≤N,1≤y≤M,A[x][y]1dist(A[i][j],A[x][y]) **数据规模**1 N 1000 **分析**这里我们可以用多源宽搜来做等价于虚拟的单源宽搜。我们可以先将所有为1的点加入队列中并将该点的距离标记为0。然后进行宽搜。每次搜索到一个合法的位置我们就更新当前点的距离 d i s [ n x ] [ n y ] d i s [ x ] [ y ] 1 dis[nx][ny] dis[x][y] 1 dis[nx][ny]dis[x][y]1 **优化**无 题解: 见分析 TIPS无 时间复杂度O(N^2) #includecstring
#includeiostream
#includealgorithm
#includequeueusing namespace std;
typedef pairint, int PII;
const int N 1010;int dx[4] {-1, 1, 0, 0}, dy[4] {0, 0, -1, 1};
char g[N][N];
int dis[N][N];
int n, m;bool check(int x, int y){if(x 0 || x n || y 0 || y m) return false;return dis[x][y] -1;
}
void bfs(){memset(dis, -1, sizeof dis);queuePII q;for(int i 0; i n; i){for(int j 0; j m; j){if(g[i][j] 1){q.push({i, j});dis[i][j] 0;}}}while(q.size()){auto t q.front();q.pop();int x t.first, y t.second;for(int i 0; i 4; i){int nx x dx[i], ny y dy[i];if(check(nx, ny)){dis[nx][ny] dis[x][y] 1;q.push({nx, ny});}}}
}int main(){cin n m;for(int i 0; i n; i) scanf(%s, g[i]);bfs();for(int i 0; i n; i){for(int j 0; j m; j) printf(%d , dis[i][j]);puts();}return 0;
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Main().run();}final int N 1010;class Pair{int x, y;public Pair(int x, int y) {this.x x;this.y y;}}char[][] g new char[N][N];int[][] dis new int[N][N];int[] dx {-1, 1, 0, 0}, dy {0, 0, -1, 1};int n, m;boolean check(int x, int y){if(x 0 || x n || y 0 || y m) return false;return dis[x][y] -1;}StringTokenizer stringTokenizer;BufferedReader bufferedReader new BufferedReader(new InputStreamReader(System.in));String next(){while(stringTokenizer null || !stringTokenizer.hasMoreElements()){try {stringTokenizer new StringTokenizer(bufferedReader.readLine());} catch (IOException e) {e.printStackTrace();}}return stringTokenizer.nextToken();}int nextInt(){return Integer.parseInt(next());}/*** 用于计算当前位置到1的最短距离*/void bfs(){for(int i 0; i n; i) Arrays.fill(dis[i], -1);QueuePair queue new ArrayDeque();for (int i 0; i n; i) {for (int j 0; j m; j) {if(g[i][j] 1){dis[i][j] 0;queue.offer(new Pair(i, j));}}}while(!queue.isEmpty()){Pair t queue.poll();int x t.x, y t.y;for(int i 0; i 4; i){int nx x dx[i], ny y dy[i];if(check(nx, ny)){dis[nx][ny] dis[x][y] 1;queue.offer(new Pair(nx, ny));}}}}void run(){PrintWriter out new PrintWriter(System.out);n nextInt();m nextInt();for(int i 0; i n; i) {char[] str next().toCharArray();for(int j 0; j m; j) {g[i][j] str[j];}}bfs();for(int i 0; i n; i){for(int j 0; j m; j) out.print(dis[i][j] );out.println();}out.flush();out.close();}
} 题目描述 推箱子你将控制一个人把一个箱子推到目的地。给定一张n行m列的地图用.表示空地字符#表示墙字符S表示人的初始位置字符B表示箱子的起始位置字符T表示箱子的目标位置。求一种方案使得箱子的移动次数最少在此基础上再让人移动的总步数最少。方案中使用大写的EWSN表示箱子的移动使用小写的ewsn表示人的移动。 **数据规模**1 N 20 分析 箱子移动的次数最少人的移动次数最少移动箱子的操作序列的字典序最小移动人的操作序列的字典序最小 **优化**无 题解: 见分析 TIPS无 时间复杂度O(MN)^2 #includeiostream
#includealgorithm
#includecstring
#includevector
#includequeue
using namespace std;
typedef pairint, int PII;
const int N 25;
int dx[4] {1, -1, 0, 0};//上下左右,
int dy[4] {0, 0, 1, -1};
char ops[5] nswe;struct Point{int x, y, dir;
};int n, m;
char g[N][N];
PII dist[N][N][4]; //存到每个状态的最短距离first存箱子的移动距离second存人的移动距离
Point pre[N][N][4];//存箱子从哪个状态转移过来的
vectorint path[N][N][4];//存到每个状态的路径
bool st[N][N][4], vis[N][N];//对箱子做bfs时用st判重对人做bfs时用vis判重
int preman[N][N];//存人是从哪个状态转移过来的bool check(int x, int y){return ~x ~y x n y m g[x][y] ! #;
}
/*** 对人做宽搜。判断人是否能从start走到end且不经过box若能将路景观存入seq中并返回长度若不能返回-1* param start* param end* param box* param seq* return*/
int bfs_man(PII start, PII end, PII box, vectorint seq){//初始化vis和premanmemset(vis,false, sizeof vis);memset(preman, -1, sizeof preman);vis[start.first][start.second] true;//start位置不能走vis[box.first][box.second] true;//box的位置不能走queuePII q;q.push(start);while(q.size()){auto t q.front();q.pop();int x t.first, y t.second;//如果走到终点if(t end){seq.clear();while(~preman[x][y]){int dir preman[x][y];seq.push_back(dir);x dx[dir];y dy[dir];//x和y按相反的方向走回去}return seq.size();//返回路径的长度}for(int i 0; i 4; i){//由于dx和dy存的是人对箱子的方向和所要走的四个方向是反着的//直接用 dx[i] 和 dy[i]也能遍历四个方向但是无法保证字典序最小//所以这里要反过来用, -dx[i], -dy[i]int a x - dx[i], b y - dy[i];if(!check(a, b) || vis[a][b]) continue;//若(a, b)不能走就跳过vis[a][b] true;//标记preman[a][b] i;//记录方向q.push({a, b}); //入队}}return -1;//没有就返回-1
}
/*** 对箱子做宽搜并返回是否能到终点* param start* param box* param end* return*/
bool bfs_box(PII start, PII box, Point end){memset(st, false, sizeof st);queuePoint q;//枚举位置for(int i 0; i 4; i){int a box.first dx[i], b box.second dy[i];//人要走的位置int c box.first - dx[i], d box.second - dy[i];//箱子推到的位置if(!check(a, b) || !check(c, d)) continue; //若不合法就跳过vectorint seq;int len bfs_man(start, {a, b}, box, seq);//从start到(a, b)且不经过box将路径存入seq中if(len -1) continue;q.push({c, d, i});st[c][d][i] true;//标记path[c][d][i] seq;//到该点的路径为seqdist[c][d][i] {1, len};//到该点的距离为 箱子被推了1步人走了len步//记录该点是从{box.first, box.second}到达的为了方便将方向置为-1pre[c][d][i] {box.first, box.second, -1};}PII maxd {1e9, 1e9};// 存到终点的距离while(q.size()){auto t q.front();q.pop();PII v dist[t.x][t.y][t.dir];//取出队头状态的距离//如果达到了终点并且距离比maxd更小那么更行if(g[t.x][t.y] T v maxd){end t;maxd v;}for(int i 0; i 4; i){int a t.x dx[i], b t.y dy[i];//人要走的位置int c t.x - dx[i], d t.y - dy[i];//箱子要走的位置if(!check(a, b) || !check(c, d)) continue;vectorint seq;//箱子是从t.dir的方向被推过来的所有推之前的位置就是(t.x dx[t.dir], t.y dy[t.dir])//所以推完之后人的位置就在(t.x dx[t.dir], ty dy[t.dir])int len bfs_man({t.x dx[t.dir], t.y dy[t.dir]}, {a, b}, {t.x, t.y}, seq);if(len -1) continue;PII distance {v.first 1, v.second len};//能到这个状态就更新if(!st[c][d][i]){//若当前状态未到过q.push({c, d, i});//入队st[c][d][i] true;path[c][d][i] seq;dist[c][d][i] distance;pre[c][d][i] t;}else if(dist[c][d][i] distance){//若此次距离更近dist[c][d][i] distance;path[c][d][i] seq;pre[c][d][i] t;}}}return maxd.first ! 1e9;//更新过
}
int main(){int T 1;while(cin n m, n || m){printf(Maze #%d\n, T);//读入地图for(int i 0; i n; i) cin g[i];PII start, box;//找到人的位置和箱子的位置存入start和box中for(int i 0; i n; i){for(int j 0; j m; j){if(g[i][j] S) start {i, j};else if(g[i][j] B) box {i, j};}}Point end; string ans;//end存终点的位置ans存答案这里end在bfs中记录if(!bfs_box(start, box, end)) ans Impossible.;else{while(~end.dir){ans ops[end.dir] - 32;//将小写字母转为大写字母for(int i 0; i path[end.x][end.y][end.dir].size(); i){ans ops[path[end.x][end.y][end.dir][i]];//存入移动的路径}end pre[end.x][end.y][end.dir]; //end往前倒着找}reverse(ans.begin(), ans.end());//由于记录的序列是倒着的这里需要翻转}cout ans endl endl;}return 0;
} import java.util.*;public class Main {public static void main(String[] args) {new Main().run();}final int N 25;int[] dx {1, -1, 0, 0}, dy {0, 0, 1, -1};//上下左右char[] ops {n, s, w, e};class Point{int x, y, dir;//当前点的坐标以及从哪个方向转移过来public Point(int x, int y, int dir) {this.x x;this.y y;this.dir dir;}Overridepublic String toString() {return Point{ x x , y y , dir dir };}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Point point (Point) o;return x point.x y point.y dir point.dir;}Overridepublic int hashCode() {return Objects.hash(x, y, dir);}}class Pair{int f, s;public Pair(int f, int s) {this.f f;this.s s;}Overridepublic String toString() {return Pair{ f f , s s };}Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Pair pair (Pair) o;return f pair.f s pair.s;}Overridepublic int hashCode() {return Objects.hash(f, s);}}int n, m;char[][] g new char[N][];Pair[][][] dist new Pair[N][N][4]; //存到每个状态的最短距离first存存箱子的移动距离second存人的移动距离Point[][][] pre new Point[N][N][4];//存箱子从哪个状态转移过来ListInteger[][][] path new List[N][N][4];//存到每个状态的路径boolean[][][] st new boolean[N][N][4];//存对箱子搜索时进行判重boolean[][] vis new boolean[N][N];//存对人搜索时判重int[][] preman new int[N][N];//存人是从哪个状态转移过来的/*** 判断当前位置是否可以走* param x* param y* return*/boolean check(int x, int y){if(x 0 || x n || y 0 || y m) return false;return g[x][y] ! #;}/*** 前面一个比后面一个小* param a* param b* return*/boolean compare(Pair a, Pair b){if(a.f b.f) return true;if(a.f b.f a.s b.s) return true;return false;}ListInteger seq new ArrayList();/*** 搜索人从起点到终点不经过box的最短步数这里若可以到达终点将路线存入seq中* param start* param end* param box* return 返回步数*/int bfsMan(Pair start, Pair end, Pair box){for(int i 0; i n; i) {Arrays.fill(vis[i], false);Arrays.fill(preman[i], -1);}vis[start.f][start.s] true;vis[box.f][box.s] true;QueuePair q new ArrayDeque();q.offer(start);while(!q.isEmpty()){Pair t q.poll();//System.out.println(t);int x t.f, y t.s;//若走到终点if(t.equals(end)){seq.clear();while(preman[x][y] 0){int dir preman[x][y];seq.add(dir);//往相仿方向走回去x dx[dir];y dy[dir];}return seq.size();}for(int i 0; i 4; i){//这里dx和dy是存的人对箱子的方向int a x - dx[i], b y - dy[i];//System.out.println(a : a b b);//if(a 0 b 1) System.out.println(vis : vis[0][1]);if(!check(a, b) || vis[a][b]) continue;;vis[a][b] true;preman[a][b] i;q.add(new Pair(a, b));}}return -1;}Point end;/*** 对箱子进行宽搜返回是否能到终点* param start* param box* return*/boolean bfsBox(Pair start, Pair box){for (int i 0; i n; i) {for(int j 0; j m; j) Arrays.fill(st[i][j], false);}QueuePoint q new ArrayDeque();//枚举位置for(int i 0; i 4; i){int a box.f dx[i], b box.s dy[i];//人要走的位置int c box.f - dx[i], d box.s - dy[i];//箱子要推到的位置if(!check(a, b) || !check(c, d)) continue;seq.clear();int len bfsMan(start, new Pair(a, b), box);if(len -1) continue;q.offer(new Point(c, d, i));st[c][d][i] true;path[c][d][i] new ArrayList(seq);dist[c][d][i] new Pair(1, len);//箱子被推了一步人走了len步pre[c][d][i] new Point(box.f, box.s, -1);}Pair maxd new Pair((int)1e9, (int)1e9);while(!q.isEmpty()){Point t q.poll();Pair v dist[t.x][t.y][t.dir];if(g[t.x][t.y] T compare(v, maxd)){end new Point(t.x, t.y, t.dir);maxd new Pair(v.f, v.s);}for(int i 0; i 4; i){int a t.x dx[i], b t.y dy[i];//人要走的位置int c t.x - dx[i], d t.y - dy[i];//箱子要走的位置if(!check(a, b) || !check(c, d)) continue;;seq.clear();int len bfsMan(new Pair(t.x dx[t.dir], t.y dy[t.dir]), new Pair(a, b), new Pair(t.x, t.y));if(len -1) continue;Pair distance new Pair(v.f 1, v.s len);if(!st[c][d][i]){q.offer(new Point(c, d, i));st[c][d][i] true;path[c][d][i] new ArrayList(seq);dist[c][d][i] new Pair(distance.f, distance.s);pre[c][d][i] t;}else if(compare(distance, dist[c][d][i])){dist[c][d][i] new Pair(distance.f, distance.s);path[c][d][i] new ArrayList(seq);pre[c][d][i] new Point(t.x, t.y, t.dir);}}}return maxd.f ! (int) 1e9;}void run(){Scanner sc new Scanner(System.in);int T 1;while(true){n sc.nextInt();m sc.nextInt();if(n 0 m 0) break;System.out.printf(Maze #%d\n, T);//写入地图for(int i 0; i n; i){g[i] sc.next().toCharArray();}//记录起点和箱子位置Pair start new Pair(-1, -1), box new Pair(-1, -1);for(int i 0; i n; i){for(int j 0; j m; j){if(g[i][j] S) start new Pair(i, j);if(g[i][j] B) box new Pair(i, j);}}end new Point(-1, -1, -1);String ans;if(!bfsBox(start, box)) ans Impossible.;else{StringBuilder stringBuilder new StringBuilder();while(end.dir 0){stringBuilder.append((char)(ops[end.dir] - 32));//将大写字母转化为小写字母for(int i 0; i path[end.x][end.y][end.dir].size(); i){stringBuilder.append(ops[path[end.x][end.y][end.dir].get(i)]);//存入路径}end pre[end.x][end.y][end.dir];}stringBuilder.reverse();ans stringBuilder.toString();}System.out.println(ans \n);}sc.close();}
}题目描述给定一个图图中路径有两种表示\或/改变路径所花费的体力为1 不改变花费体力为0现在想从(0, 0)到达终点(n, m),求最小的体力消耗。 **数据规模**1 N 500 **分析**典型的图论问题这里使用优化版的Dijkstra算法来实现 优化 我们使用双端队列当要去的点的坐标和图中路径的方向相同时我们将要去的点加入队头否则加入队尾。这样就保障了队列是路径长度是单调递增的。使用标记数组标记当前点是否访问过若已经访问过则跳过该点。若当前点的坐标为终点直接返回该点的路径。 题解: 见分析 TIPS 这里dx、dy存储的是当前点到要去的点的偏移量。即点和点的关系。ix、iy存储的是当前点和要去点的之间隔着的方块坐标就是当前点与方块坐标的偏移量。即点和方块的关系。 时间复杂度O(m*n) #includeiostream
#includecstring
#includedequeusing namespace std;
typedef pairint, int PII;
const int N 510;int n, m;
char g[N][N];
int dis[N][N];
int dx[4] {-1, -1, 1, 1}, dy[4] {-1, 1, 1, -1};
int ix[4] {-1, -1, 0, 0}, iy[4] {-1, 0, 0, -1};
char cs[] \\/\\/;
int bfs(PII p){memset(dis, 0x3f, sizeof dis);dequePII dq;dis[0][0] 0;dq.push_back(p);while(dq.size()){auto t dq.front();dq.pop_front();int x t.first, y t.second;for(int i 0; i 4; i){int a x dx[i], b y dy[i];if(a 0 a n b 0 b m){int w 0;int c x ix[i], d y iy[i];if(g[c][d] ! cs[i]) w 1;if(dis[a][b] dis[x][y] w){dis[a][b] dis[x][y] w;if(w) dq.push_back({a, b});else dq.push_front({a, b});}}}}return dis[n][m] 0x3f3f3f3f ? -1 : dis[n][m];
}
int main(){int T;scanf(%d, T);while(T--){cin n m;for(int i 0; i n; i) scanf(%s, g[i]);int ans bfs({0, 0});if(ans -1) puts(NO SOLUTION);else printf(%d\n, ans);}return 0;
}import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 510, INF (int) 1e9;char[][] g new char[N][];boolean[][] st new boolean[N][N];char[] str {\\, /, \\, /};int[][] dis new int[N][N];int[] dx {-1, -1, 1, 1}, dy {-1, 1, 1, -1};//存点和点的关系int[] ix {-1, -1, 0, 0}, iy {-1, 0, 0, -1};//存点和格子的关系class Pair{int x, y;public Pair(int x, int y) {this.x x;this.y y;}}int n, m;int bfs(){for (int i 0; i n; i) {Arrays.fill(st[i], false);Arrays.fill(dis[i], INF);}DequePair deque new ArrayDeque();dis[0][0] 0;deque.offer(new Pair(0, 0));while(!deque.isEmpty()){Pair t deque.poll();int x t.x, y t.y;if(st[x][y]) continue;if(x n y m) return dis[x][y];st[x][y] true;for(int i 0; i 4; i){int a x dx[i], b y dy[i];if(a 0 a n b 0 b m){int w 0;int c x ix[i], d y iy[i];//用当前点的坐标计算出对应格子的坐标if(g[c][d] ! str[i]) w 1;//若相同则不必旋转边权位0反之为1//dijkstra算法if(dis[a][b] dis[x][y] w){dis[a][b] dis[x][y] w;//根据权值加入队头或队尾if(w 0) deque.offer(new Pair(a, b));else deque.offerFirst(new Pair(a, b));}}}}return dis[n][m] INF ? -1 : dis[n][m];}void run(){Scanner sc new Scanner(System.in);int T sc.nextInt();while(T-- 0){n sc.nextInt();m sc.nextInt();for (int i 0; i n; i) {g[i] sc.next().toCharArray();}int t bfs();if(t -1) System.out.println(NO SOLUTION);else System.out.println(t);}sc.close();}
}题目描述有N个城市(编号0、1…N-1) 和 M 条道路构成一张无向图。每个城市里有一个加油站不同加油站的单位油价可能不一样。现在给定k个询问每个询问问你一辆油箱容量为C的汽车从a 到 b城市最少的花费是多少(起始时汽车没有油) **数据规模**1 N 1000, 1 M 10000, 1 C 100 **分析**典型的图论问题这里使用Dijkstra算法来实现 **优化**无 题解: 该问题中每个点可能有不同的油量。在求最短路问题中可以将一个点拆分成多个点。这里我们将不同的容量拆成不同的点。 当前点可以加油时且加油后能使得总成本更小就就加油并更新dist当前点可以到达其它点且能使得总成本更小就更新dist TIPS无 时间复杂度O((nm)*logn) #includeiostream
#includecstring
#includequeueusing namespace std;
const int N 1010, M 20010, C 110;
struct Point{int d, u, c;//分别存油钱、点的编号、剩余油量/*** 重载小于号按大于号反过来重载小于号后面建堆时建大顶堆* param t* return*/bool operator (const Point t) const{return d t.d;}
};
int n, m;
int price[N];
int h[N], e[M], w[M], ne[M], idx;
int dist[N][C];
bool st[N][C];void add(int a, int b, int c){e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}int dijkstra(int c, int start, int end){priority_queuePoint heap;memset(dist, 0x3f, sizeof dist);memset(st, false, sizeof st);heap.push({0, start, 0});dist[start][0] 0;while(heap.size()){auto t heap.top();heap.pop();if(t.u end) return t.d;if(st[t.u][t.c]) continue;st[t.u][t.c] true;if(t.c c){//可以加油if(dist[t.u][t.c 1] t.d price[t.u]){//若这次加油后油钱比之前低dist[t.u][t.c 1] t.d price[t.u];heap.push({dist[t.u][t.c 1], t.u, t.c 1});}}for(int i h[t.u]; ~i; i ne[i]){//遍历所有边if(t.c w[i]){//若当前剩余油量可以到if(dist[e[i]][t.c - w[i]] t.d){//若这次到该点的油钱小于原来就更新dist[e[i]][t.c - w[i]] t.d;heap.push({t.d, e[i], t.c - w[i]});}}}}return -1;
}
int main(){cin n m;for(int i 0; i n; i) scanf(%d, price[i]);memset(h, -1, sizeof h);while(m--){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);add(b, a, c);}int query;scanf(%d, query);while(query--){int c, s, e;scanf(%d%d%d, c, s, e);int t dijkstra(c, s, e);if(t -1) puts(impossible);else printf(%d\n, t);}return 0;
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;public class Main {public static void main(String[] args) {new Main().run();}final int N 1010, M 20010, C 110, INF 0x3f3f3f3f;class Point{int d, u, c;//分别表示当前油钱、点编号、剩余油public Point(int s, int u, int c) {this.d s;this.u u;this.c c;}}int n, m;int[] price new int[N];int[] h new int[N], e new int[M], ne new int[M], w new int[M];int idx 0;int[][] dist new int[N][C];boolean[][] st new boolean[N][C];void add(int a, int b, int c){e[idx] b;w[idx] c;ne[idx] h[a];h[a] idx;}StreamTokenizer streamTokenizer new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));int nextInt(){try {streamTokenizer.nextToken();} catch (IOException ioException) {ioException.printStackTrace();}return (int) streamTokenizer.nval;}int bfs(int c, int start, int end){PriorityQueuePoint heap new PriorityQueue(Comparator.comparingInt(a - a.d));//默认for(int i 0; i n; i){Arrays.fill(dist[i], INF);Arrays.fill(st[i], false);}heap.add(new Point(0, start, 0));dist[start][0] 0;while(!heap.isEmpty()){Point t heap.poll();//特判if(t.u end) return t.d;//当已经到达终点if(st[t.u][t.c]) continue;//当前点已访问就跳过st[t.u][t.c] true;//当该点可以加油且可以使得成本更小if(t.c c){if(dist[t.u][t.c 1] t.d price[t.u]){dist[t.u][t.c 1] t.d price[t.u];heap.add(new Point(dist[t.u][t.c 1], t.u, t.c 1));}}//当该点的边可以到达且可以使得成本更小for(int i h[t.u]; i ! -1; i ne[i]){if(t.c w[i]){if(dist[e[i]][t.c - w[i]] t.d){dist[e[i]][t.c - w[i]] t.d;heap.add(new Point(t.d, e[i], t.c - w[i]));}}}}return -1;}void run(){n nextInt();m nextInt();for(int i 0; i n; i) price[i] nextInt();Arrays.fill(h, -1);while(m-- 0){int a nextInt(), b nextInt(), c nextInt();add(a, b, c);add(b, a, c);}int q nextInt();while(q-- 0){int c nextInt(), s nextInt(), e nextInt();int t bfs(c, s, e);if(t -1) System.out.println(impossible);else System.out.println(t);}}
}题目描述给定一张n * m的地图地图中给出男孩、女孩和两个幽灵的坐标。男孩和女孩可以往上下左右四个方向移动其中男孩每秒钟可以运动3个单位即移动三次。女孩可以每秒钟移动一个单位即一次。幽灵则会在一秒钟内同时向四个方向进行扩展扩展后的范围是原位置对应位置曼哈顿距离不超过2所构成的面积。每次移动时幽灵会先移动然后男孩和女孩才能移动。现在我们想知道在不遇到幽灵的情况下男孩和女孩会和的最短时间是多少? **数据规模**1 n, m 800 **分析**两个人可以分别进行扩展这里我们可以同时使用两个bfs即双向bfs分别进行扩展。这里判断某个点对应时刻是否在幽灵扩展的范围内只需要用曼哈顿距离的求法即纵坐标之差的绝对值加横坐标之差的绝对值。 优化 当两个队列中有一个为空时说明无处可走了可以提前结束。队列中每次弹出元素时先判断该元素是否是合法的再考虑其它操作。 题解:见分析 TIPS无 时间复杂度O(T*N^2) #includeiostream
#includecstring
#includequeue
#includealgorithmusing namespace std;
typedef pairint, int PII;
const int N 810;
char g[N][N];
int st[N][N];
PII boy, girl, ghost[2];int n, m;const int dx[4] {-1, 1, 0, 0}, dy[4] {0, 0, -1, 1};
bool check(int x, int y, int step){if(x 0 || x n || y 0 || y m || g[x][y] X) return false;for(int i 0; i 2; i){if(abs(ghost[i].first - x) abs(ghost[i].second - y) 2 * step) return false;}return true;
}
int bfs(){memset(st, 0, sizeof st);queuePII qb, qg;qb.push(boy), qg.push(girl);int step 0;while(qb.size() qg.size()){step;for(int i 0; i 3; i){for(int j 0, len qb.size(); j len; j){auto t qb.front();qb.pop();int x t.first, y t.second;if(!check(x, y, step)) continue;for(int k 0; k 4; k){int nx x dx[k], ny y dy[k];if(check(nx, ny, step)){if(st[nx][ny] 2) return step;if(!st[nx][ny]){st[nx][ny] 1;qb.push({nx, ny});}}}}}for(int i 0; i 1; i){for(int j 0, len qg.size(); j len; j){auto t qg.front();qg.pop();int x t.first, y t.second;if(!check(x, y, step)) continue;for(int k 0; k 4; k){int nx x dx[k], ny y dy[k];if(check(nx, ny, step)){if(st[nx][ny] 1) return step;if(!st[nx][ny]){st[nx][ny] 2;qg.push({nx, ny});}}}}}}return -1;
}
int main(){int T;scanf(%d, T);while(T--){scanf(%d%d, n, m);for(int i 0; i n; i) scanf(%s, g[i]);int cnt 0;for(int i 0; i n; i)for(int j 0; j m; j)if(g[i][j] M) boy {i, j};else if(g[i][j] G) girl {i, j};else if(g[i][j] Z) ghost[cnt] {i, j};printf(%d\n, bfs());}return 0;
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Main().run();}final int N 810;char[][] g new char[N][];int[][] st new int[N][N];int[] dx {-1, 1, 0, 0}, dy {0, 0, -1, 1};class Pair{int f, s;public Pair(int f, int s) {this.f f;this.s s;}}StringTokenizer stringTokenizer;BufferedReader bufferedReader new BufferedReader(new InputStreamReader(System.in));String next(){while(stringTokenizer null || !stringTokenizer.hasMoreElements()){try {stringTokenizer new StringTokenizer(bufferedReader.readLine());} catch (IOException e) {e.printStackTrace();}}return stringTokenizer.nextToken();}int nextInt(){return Integer.parseInt(next());}int n, m;Pair boy, girl, ghost[] new Pair[2];boolean check(int x, int y, int step){if(x 0 || x n || y 0 || y m || g[x][y] X) return false;for (int i 0; i 2; i)if(Math.abs(x - ghost[i].f) Math.abs(y - ghost[i].s) 2 * step) return false;return true;}int bfs(){for (int i 0; i n; i) {Arrays.fill(st[i], 0);}QueuePair qb new ArrayDeque(), qg new ArrayDeque();qb.offer(boy);qg.offer(girl);int step 0;while(!qb.isEmpty() !qg.isEmpty()){step;for(int i 0; i 3; i){for(int j 0, len qb.size(); j len; j){Pair t qb.poll();int x t.f, y t.s;if(!check(x, y, step)) continue;for (int k 0; k 4; k) {int nx x dx[k], ny y dy[k];if(check(nx, ny, step)){if(st[nx][ny] 2) return step;if(st[nx][ny] 0){st[nx][ny] 1;qb.offer(new Pair(nx, ny));}}}}}for(int i 0; i 1; i){for(int j 0, len qg.size(); j len; j){Pair t qg.poll();int x t.f, y t.s;if(!check(x, y, step)) continue;for (int k 0; k 4; k) {int nx x dx[k], ny y dy[k];if(check(nx, ny, step)){if(st[nx][ny] 1) return step;if(st[nx][ny] 0){st[nx][ny] 2;qg.offer(new Pair(nx, ny));}}}}}}return -1;}void run(){int T nextInt();while(T-- 0){n nextInt();m nextInt();for(int i 0; i n; i) g[i] next().toCharArray();int cnt 0;for(int i 0; i n; i){for (int j 0; j m; j) {if(g[i][j] M) boy new Pair(i, j);else if(g[i][j] G) girl new Pair(i, j);else if(g[i][j] Z) ghost[cnt] new Pair(i, j);}}System.out.println(bfs());}}
} 题目描述给定一张N个点、M条边的有向图求从起点S到终点T的第K短路长度? (路径允许重复经过点或边,这里边的权值非负) **数据规模**1 S, T, K N 1e3, 0 M 1e4 **分析**点数非常多、边的权值非负可以使用启发式算法来优化宽搜。 优化 建立一个启发式函数来取代小根堆直接根据距离起点的距离来出队。当某个点已经出队了k次就不需要再更新它了。 题解: 建立反图然后在反向图上求出从T到其它所有点的最短距离作为每个点的估价函数。从S开始扩展每次取出当前的估计值最小的点将其能扩展到的所有点全扩展。 估计值 距离起点的距离 估价函数当第K次遇到T时就求出了从S到T的第K短路。 TIPS无 时间复杂度O((nm)*log(nm)*k) #includeiostream
#includecstring
#includequeue
#includevector
#includealgorithmusing namespace std;
typedef pairint, int PII;
struct Point{int d, t, e;bool operator (const Point t) const{return d t.d;}
};
const int N 1010, M 2e5 10, INF 0x3f3f3f3f;
int n, m;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dist[N], f[N];
int S, T, K;
int st[N];void add(int *h, int a, int b, int l){e[idx] b, w[idx] l, ne[idx] h[a], h[a] idx;
}void dijkstra(){priority_queuePII, vectorPII, greaterPII heap;//建小根堆memset(dist, 0x3f, sizeof dist);//初始化距离为正无穷dist[T] 0;//终点的距离为0heap.push({0, T});//将终点入队//当小根堆不为空时就弹出while(heap.size()){auto t heap.top();heap.pop();int u t.second;//若当前元素已访问过就跳过if(st[u]) continue;st[u] 1;//标记为已访问//遍历所有边看那些点再更新距离后离终点的距离更短了若是就更新并把该点入队for(int i h[u]; ~i; i ne[i]){int v e[i];if(dist[v] dist[u] w[i]){dist[v] dist[u] w[i];heap.push({dist[v], v});}}}//将这些值存入f中memcpy(f, dist, sizeof f);
}
/*** A*算法-启发式算法* return*/
int a_star() {priority_queuePoint, vectorPoint, greaterPoint heap;//新建一个小根堆//小根堆的元素结构是{当前点距离终点的距离 当前点距离起点的距离 当前点id}heap.push({f[S], 0, S});memset(st, 0, sizeof st);//初始化次数为0//当队列不为空while(heap.size()){auto t heap.top();heap.pop();//获取当前点的坐标以及走过的距离int u t.e, distance t.t;//当前点访问次数大于k就不需要再更新了if(st[u] K) continue;st[u];//当前点次数1if(u T st[u] K) return distance;//当该点为终点时且是第k次遇到就返回当前走过的距离//遍历所有边for(int i h[u]; ~i; i ne[i]){int v e[i];//当整段长度为正无穷时就跳过说明没有路径可走if(distance w[i] dist[v] INF / 2) continue;//当下个点的次数小于k时就将新的长度加入队列中if(st[v] K){heap.push({distance w[i] f[u], distance w[i], v});}}}return -1;
}
int main(){scanf(%d%d, n, m);memset(h, -1, sizeof h);memset(rh, -1, sizeof rh);while(m--){int a, b, c;scanf(%d%d%d, a, b, c);add(h, a, b, c), add(rh, a, b, c);}scanf(%d%d%d, S, T, K);if(S T) K;dijkstra();printf(%d\n, a_star());return 0;
}import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}class Pair{int f, s;public Pair(int f, int s) {this.f f;this.s s;}}class Point{int d, t, u;public Point(int d, int t, int u) {this.d d;this.t t;this.u u;}}final int N 1010, M 200010, INF 0x3f3f3f3f;int n, m;int s, t, k;int[] h new int[N], rh new int[N], e new int[M], w new int[M], ne new int[M];int idx 0;int[] dist new int[N], st new int[N], f new int[N];void add1(int a, int b, int c){e[idx] b;w[idx] c;ne[idx] h[a];h[a] idx;}void add2(int a, int b, int c){e[idx] b;w[idx] c;ne[idx] rh[a];rh[a] idx;}void dijkstra(){Arrays.fill(dist, INF);PriorityQueuePair heap new PriorityQueue(Comparator.comparingInt(a - a.s));dist[t] 0;heap.offer(new Pair(t, 0));while(!heap.isEmpty()){Pair auto heap.poll();int u auto.f;if(st[u] ! 0) continue;st[u] 1;for(int i h[u]; i ! -1; i ne[i]){int v e[i];if(dist[v] dist[u] w[i]){dist[v] dist[u] w[i];heap.offer(new Pair(v, dist[v]));}}}System.arraycopy(dist, 0, f, 0, n);}int AStar(){Arrays.fill(st, 0);PriorityQueuePoint heap new PriorityQueue(Comparator.comparingInt(a - a.d));heap.offer(new Point(f[s], 0, s));while(!heap.isEmpty()){Point auto heap.poll();int u auto.u, distance auto.t;if(st[u] k) continue;st[u];if(st[u] k u t) return distance;for(int i h[u]; i ! -1; i ne[i]){int v e[i];if(distance w[i] f[v] INF / 2) continue;if(st[v] k){heap.offer(new Point(distance w[i] f[u], distance w[i], v));}}}return -1;}void run(){Scanner sc new Scanner(System.in);n sc.nextInt();m sc.nextInt();Arrays.fill(h, -1);Arrays.fill(rh, -1);for (int i 0; i m; i) {int a sc.nextInt(), b sc.nextInt(), c sc.nextInt();add1(a, b, c);add2(a, b, c);}s sc.nextInt();t sc.nextInt();k sc.nextInt();sc.close();if(s t) k;dijkstra();System.out.println(AStar());}
}题目描述给定一个3*3的网格其中每个位置对应一个数字或为x其中数字为从1~8中的唯一数字。我们的目的是通过交换使得网格变为正确排列。 **数据规模**n 3 **分析**这里可以使用启发式算法结合广度优先来求。启发式函数就是该状态到正确排列状态的曼哈顿距离之和。 优化 我们可以先对该字符串求逆序对个数若为偶数可以直接输出不存在。使用启发式函数对广度优先进行优化 题解:见分析 TIPS无 时间复杂度O(n*n*logn) #includeiostream
#includequeue
#includealgorithm
#includeunordered_mapusing namespace std;
typedef pairstring, char PSC;
typedef pairint, string PIS;
#define x first
#define y secondint dx[4] {-1, 1, 0, 0}, dy[4] {0, 0, -1, 1};
char ops[5] udlr;/*** 计算当前状态离目标状态的曼哈顿距离之和* param state* return*/
int f(string state){int ans 0;for(int i 0; i 9; i){if(state[i] ! x){int t state[i] - 1;ans abs(t / 3 - i / 3) abs(t % 3 - i % 3);}}return ans;
}string bfs(string start){string end 12345678x;unordered_mapstring, int dist;//存当前状态与终点的最短距离unordered_mapstring, bool st;//标记当前状态是否已访问unordered_mapstring, PSC prev;//存之前状态转移到当前转态的方向priority_queuePIS, vectorPIS, greaterPIS heap;//前者存最少步数后者存状态heap.push({f(start), start});dist[start] 0;while(heap.size()){auto t heap.top();heap.pop();string state t.y;if(state end) break;if(st[state]) continue;st[state] true;int x, y;for(int i 0; i state.size(); i){if(state[i] x){x i / 3, y i % 3;break;}}string source state;//遍历四个方向for(int i 0; i 4; i){int nx x dx[i], ny y dy[i];//看是否在范围内if(nx 0 nx 3 ny 0 ny 3){//与上下左右位置互换state source;swap(state[x * 3 y], state[nx * 3 ny]);//若当前状态未访问过或使用当前状态扩展能使得距离更短if(!dist.count(state) || dist[state] dist[source] 1){dist[state] dist[source] 1;prev[state] {source, ops[i]};heap.push({dist[state] f(state), state});}}}}string ans;while(end ! start){ans prev[end].y;end prev[end].x;}reverse(ans.begin(), ans.end());return ans;}
int main(){string start, seq;char c;for(int i 0; i 9; i){cin c;start c;if(c ! x) seq c;}int cnt 0;//计算逆序对的个数若逆序对为奇数则无解for (int i 0; i 8; i )for (int j i 1; j 8; j )if (seq[i] seq[j])cnt ;if (cnt % 2) puts(unsolvable);else cout bfs(start) endl;return 0;
}import java.util.*;public class Main {public static void main(String[] args) {new Main().run();}class PairK, V{K key;V value;public Pair(K key, V value) {this.key key;this.value value;}public K getKey() {return key;}public V getValue() {return value;}}final int[] dx {-1, 1, 0, 0}, dy {0, 0, -1, 1};final char[] ops {u, d, l, r};String bfs(String start) {String end 12345678x;MapString, Integer dist new HashMap();//记录当前状态的最少步数MapString, Boolean st new HashMap();//标记数组MapString, PairString, Character prev new HashMap();//记录原状态转移的方向PriorityQueuePairInteger, String heap new PriorityQueue(Comparator.comparingInt(Pair::getKey));heap.offer(new Pair(f(start), start));dist.put(start, 0);while (!heap.isEmpty()) {PairInteger, String t heap.poll();String state t.value;if(state.equals(end)) break;//若当前点为终点说明已经找到结束循环if(st.getOrDefault(state, false)) continue;//若当前状态已存在就跳过st.put(state, true);//标记为已访问//求x的坐标int x 0, y 0;for(int i 0; i 9; i){if(state.charAt(i) x){x i / 3;y i % 3;break;}}//source初始为当前状态String source state;//向四周进行扩展for(int i 0; i 4; i){int nx x dx[i], ny y dy[i];//当该位置合法时if(nx 0 nx 3 ny 0 ny 3){//更新当前状态为sourcestate source;//将状态转为数组交换这两个字符char[] stateA state.toCharArray();char tmp stateA[x * 3 y];stateA[x * 3 y] stateA[nx * 3 ny];stateA[nx * 3 ny] tmp;state new String(stateA);//当不含当前状态或此次更新能使得state的距离更短if(!dist.containsKey(state) || dist.get(state) dist.get(source) 1){dist.put(state, dist.get(source) 1);//就对路径进行更新prev.put(state, new Pair(source, ops[i]));//并记录原状态转移的方向heap.add(new Pair(dist.get(state) f(state), state));//将f[state] dist[state]重新加入队列中}}}}StringBuilder ans new StringBuilder();//当end和start不等时while(!end.equals(start)){//在ans中添加上一个转移过来的方向ans.append(prev.get(end).value);//并把end向前移动end prev.get(end).key;}return ans.reverse().toString();}/*** 启发式算法* param state* return*/int f(String state){int ans 0;char[] chars state.toCharArray();for (int i 0; i 9; i) {if(chars[i] ! x){int t chars[i] - 1;ans Math.abs(i / 3 - t / 3) Math.abs(i % 3 - t % 3);}}return ans;}void run(){String start , seq new String();Scanner sc new Scanner(System.in);for(int i 0; i 9; i){char c sc.next().charAt(0);start c;if(c ! x) seq c;}int cnt 0;//计算逆序对个数for(int i 0; i 8; i){for(int j i 1; j 8; j){if(seq.charAt(i) seq.charAt(j)) cnt;}}if(cnt % 2 ! 0) System.out.println(unsolvable);else System.out.println(bfs(start));}
}题目描述给定n个数编号为1n。在每一次操作中可以抽取其中的连续一段再把当前段插到其它某个位置。我们想让书按照1n排列的顺序依次排列。 **数据规模**1 n 15 **分析**如果我们一次拿出连续的 i 个数则有 n - i 1 种连续数的方式。剩余还有 n - i 个位置可以插入。因此这些数的选法有 15 * 14 14 * 13 13 * 12 … 2 * 1。在这里把一个连续的数放到某个数的后面等价于将那个数放到连续的数的前面。因此选法有(15 * 14 14 * 13 13 * 12 … 2 * 1) / 2 560。 优化 每个状态总分支的数量是560考虑在四步之内解决最多有560^4个状态会超时。因此这里可以用IDA*来优化。 题解: 估价函数需要满足不大于实际步数在最终状态下每本书后面的书的编号应该比当前书多1每次移动最多会段开三个相连接的位置因此最多会将3个错误的连接修正所以当有tot个连接那么最少需要[tot / 3]次操作。当前估计函数可以设计为f(s) [tot / 3]这里是上取整。 TIPS无 时间复杂度O(560^4) #includeiostream
#includecstring
using namespace std;
const int N 15;int n;
int q[N];//存编号
int w[5][N];//备份/*** 估价函数* return*/
int f(){//统计非有序对的个数int tot 0;//比较相邻的两个数当后一个数不是前一个数1时就进行计数for(int i 0; i n - 1; i)if(q[i 1] ! q[i] 1) tot;//最终结果要/3下取整return (tot 2) / 3;
}
/*** 检查序列是否有序* return*/
bool check(){for(int i 0; i n; i)if(q[i] ! i 1) return false;return true;
}bool dfs(int depth, int max_depth){//剪枝若当前深度 估价函数 最大深度 就返回if(depth f() max_depth) return false;//边界条件if(check()) return true;//l、r枚举闭区间,k枚举插入的区间for(int l 0; l n; l){for(int r l; r n; r){for(int k r 1; k n; k){//备份当前层memcpy(w[depth], q, sizeof q);int x, y;//交换位置for(x r 1, y l; x k; x, y) q[y] w[depth][x];for(x l; x r; x, y) q[y] w[depth][x];if(dfs(depth 1, max_depth)) return true;//回溯memcpy(q, w[depth], sizeof q);}}}return false;
}int main(){int T;scanf(%d, T);while(T--){scanf(%d, n);for(int i 0; i n; i) scanf(%d, q[i]);int depth 0;while(depth 5 !dfs(0, depth)) depth;//迭代加深if(depth 5) puts(5 or more);else printf(%d\n, depth);}return 0;
}import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 20;int[] q new int[N];int[][] b new int[5][N];int n;int f(){int tot 0;for (int i 0; i n - 1; i) {if(q[i 1] ! q[i] 1) tot;}return (tot 2) / 3;}boolean check(){for (int i 0; i n; i) {if(q[i] ! i 1) return false;}return true;}boolean dfs(int depth, int maxDepth){if(depth f() maxDepth) return false;if(check()) return true;//这里lr分别枚举左右边界k枚举要交换的起始位置for(int l 0; l n; l){for(int r l; r n; r){for(int k r 1; k n; k){//交换之前备份一下,这里每层的状态可能不一样System.arraycopy(q, 0, b[depth], 0, n);int x, y;//这里x起始下标为区间的下一个位置y为区间的左边界将中间这快移动到前面 区间移动到kfor(x r 1, y l; x k; x, y) q[y] b[depth][x];for(x l; x r; x, y) q[y] b[depth][x];//进入下一层,入口即出口if(dfs(depth 1, maxDepth)) return true;//回溯System.arraycopy(b[depth], 0, q, 0, n);}}}return false;}void run(){Scanner sc new Scanner(System.in);int T sc.nextInt();while(T-- 0){n sc.nextInt();for (int i 0; i n; i) {q[i] sc.nextInt();}int maxDepth 0;while(maxDepth 4 !dfs(0, maxDepth)) maxDepth;if(maxDepth 4) System.out.println(maxDepth);else System.out.println(5 or more);}sc.close();}
}题目描述给定一个 #的棋盘上面有三个数字各八个。有八种操作对应 A~H,现在我们想让中间的八个数为同一个数求最少需要操作的步数。 数据规模 n 8 **分析**首先想到的是深搜对于这种图我们将对应操作的行、列存入ops中。将中间的八个数存入center 中。 因为这里需要输出路径我们将路径保存在path中。 优化 这里可以使用IDA*算法即基于逐步加深深度搜索 估价函数其中估价函数 当前值 真实值对于同一种操作如果上一个操作和当前操作的方向正好相反就不需要重复考虑。这里使用一个数组rev用来映射当前操作与之相反的操作。 题解: 估价函数可以用当前中间的八个数中重复次数最多的数作为max, 我们剩余要操作的步骤就是 8 - cnt 即 f 8 - cnt TIPS无 时间复杂度O(7^k) #includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 24;
int q[N];
int ops[8][7] {{0, 2, 6, 11, 15, 20, 22},{1, 3, 8, 12, 17, 21, 23},{10, 9, 8, 7, 6, 5, 4},{19, 18, 17, 16, 15, 14, 13},{23, 21, 17, 12, 8, 3, 1},{22, 20, 15, 11, 6, 2, 0},{13, 14, 15, 16, 17, 18, 19},{4, 5, 6, 7, 8, 9, 10}
};
int rev[8] {5, 4, 7, 6, 1, 0, 3, 2};
int center[8] {6, 7, 8, 11, 12, 15, 16, 17};
int path[100];
int cnt[3];
/*** 估价函数* return*/
int f(){memset(cnt, 0, sizeof cnt);for(int i 0; i 8; i) cnt[q[center[i]] - 1];int m 0;for(int i 0; i 3; i) m max(m, cnt[i]);return 8 - m;
}bool check(){for(int i 1; i 8; i) if(q[center[0]] ! q[center[i]]) return false;return true;
}void operate(int x){int t q[ops[x][0]];for(int i 1; i 7; i) q[ops[x][i - 1]] q[ops[x][i]];q[ops[x][6]] t;
}
bool dfs(int depth, int max_depth, int last){if(depth f() max_depth) return false;if(!f()) return true;for(int i 0; i 8; i){if(last rev[i]) continue;operate(i);path[depth] i;if(dfs(depth 1, max_depth, i)) return true;operate(rev[i]);}return false;
}
int main(){while(scanf(%d, q[0]), q[0]){for(int i 1; i N; i) scanf(%d, q[i]);int depth 0;while(!dfs(0, depth, -1)) depth;if(!depth) {puts(No moves needed);printf(%d\n, q[6]);}else{for(int i 0; i depth; i) printf(%c, path[i] A);printf(\n%d\n, q[6]);}}return 0;
} import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 24;int[] q new int[N];int[] path new int[100];int[] cnt new int[3];int[][] ops {{0, 2, 6, 11, 15, 20, 22},{1, 3, 8, 12, 17, 21, 23},{10, 9, 8, 7, 6, 5, 4},{19, 18, 17, 16, 15, 14, 13},{23, 21, 17, 12, 8, 3, 1},{22, 20, 15, 11, 6, 2, 0},{13, 14, 15, 16, 17, 18, 19},{4, 5, 6, 7, 8, 9, 10}};int[] center {6, 7, 8, 11, 12, 15, 16, 17};int[] rev {5, 4, 7, 6, 1, 0, 3, 2};int f(){Arrays.fill(cnt, 0);for(int i 0; i 8; i) cnt[q[center[i]] - 1];int max 0;for (int i 0; i 3; i) max Math.max(max, cnt[i]);return 8 - max;}boolean check(){for(int i 1; i 8; i) if(q[center[0]] ! q[center[i]]) return false;return true;}void operate(int x){int t q[ops[x][0]];for(int i 0; i 6; i) q[ops[x][i]] q[ops[x][i 1]];q[ops[x][6]] t;}boolean dfs(int depth, int maxDepth, int last){if(depth f() maxDepth) return false;if(f() 0) return true;for(int i 0; i 8; i){if(last rev[i]) continue;operate(i);path[depth] i;if(dfs(depth 1, maxDepth, i)) return true;operate(rev[i]);}return false;}void run(){Scanner sc new Scanner(System.in);while(true){q[0] sc.nextInt();if(q[0] 0) break;for (int i 1; i N; i) q[i] sc.nextInt();int depth 0;while(!dfs(0, depth, -1)) depth;if(depth 0){System.out.println(No moves needed);System.out.println(q[6]);}else{for (int i 0; i depth; i) System.out.print((char) (path[i] A));System.out.printf(\n%d\n, q[6]);}}sc.close();}
} 题目描述给定一个正方形它由若干根火柴构成正方形可能缺失了一些火柴现在我们想去除其中的一些火柴使得火柴不能构成正方形。那么至少要去除多少根火柴 数据规模 n 5 **分析**问题等价于 从现有火柴中至少选择多少根火柴能使得正方形中都被选了一根火柴。 这是重复覆盖问题可以用dfs来做。 优化 每次选择一个还没有被覆盖的正方形(选择最小的一个)枚举选择它上面的哪根火柴。估价函数设计:枚举每一个正方形若当前正方形还是完整的那么直接删掉它的所有边只记删除一次。小于等于真实值。 题解:见分析 TIPS无 时间复杂度O(60^k) #includeiostream
#includecstring
#includevectorusing namespace std;const int N 65; //网格最大是5 * 5的最多会有 5 * (5 1) * 2 60个正方形
int n, idx; //n为网络规模idx为正方形数量
vectorint square[N]; //存每个正方形的火柴编号
bool st[N]; //标记当前火柴是否已经被移除//新加一个正方形左上角坐标为(r,c)边长为len的正方形
void add(int r, int c, int len){int d n 1 | 1;//即2n 1vectorint s square[idx];//将上一组测试内容清空s.clear();for(int i 0; i len; i){//第i个s.push_back(d * r c i 1); //上s.push_back(d * (r len) c i 1);//下s.push_back((r i) * d n c 1);//左s.push_back((r i) * d n c len 1 );//左}
// for(int x : s) printf(%d , x);
// puts();idx;}
/*** 判断正方形是否完整* param s* return*/
bool check(vectorint s){for(int x : s){if(st[x]) return false;}return true;
}
/*** 估价函数,若当前正方形还是完整就删除掉它的所有边并只记一次* return*/
int f(){static bool b[N];//备份数组用于存stmemcpy(b, st, sizeof st);int ans 0;for(int i 0; i idx; i){//枚举所有正方形if(check(square[i])){ans;for(int x : square[i]){st[x] true;}}}memcpy(st, b, sizeof b);//复制回来return ans;
}
bool dfs(int depth, int max_depth){if(depth f() max_depth) return false;for(int i 0; i idx; i){//枚举所有正方形if(check(square[i])){//若第i个正方形未被破坏//就枚举该正方形的所有边并去掉该边继续搜索for(int x : square[i]){st[x] true;if(dfs(depth 1, max_depth)) return true;st[x] false;//回溯}//这里若每条边都不可行就返回falsereturn false;}}return true;//这里所有正方形都被破坏了返回true;
}
int main(){int T;scanf(%d, T);while(T--){scanf(%d, n), idx 0;//初始化idxmemset(st, false, sizeof st);for(int len 1; len n; len){//枚举len、r、c预处理每个正方形for(int r 0; r len n; r){for(int c 0; c len n; c)add(r, c, len);}}int k;scanf(%d, k);while(k--){//将这些边标记为已移除int x;scanf(%d, x);st[x] true;}int depth 0;while(!dfs(0, depth)) depth;printf(%d\n, depth);}return 0;
}import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 65;int n, idx;ListInteger[] square new List[N];boolean[] st new boolean[N];int maxDepth;void add(int r, int c, int len) {int d n 1 | 1;square[idx] new ArrayList();ListInteger s square[idx];for (int i 0; i len; i) {s.add(d * r c i 1);s.add(d * (r len) c i 1);s.add(d * (r i) c n 1);s.add(d * (r i) c n len 1);}idx;}boolean check(int s) {for (int i : square[s]) if (st[i]) return false;return true;}int f() {boolean[] b Arrays.copyOf(st, N);int cnt 0;for (int i 0; i idx; i) {if (check(i)){cnt;for (int x : square[i]) {st[x] true;}}}st Arrays.copyOf(b, N);return cnt;}boolean dfs(int depth) {if (depth f() maxDepth) return false;for (int i 0; i idx; i) {if (check(i)) {for (int x : square[i]) {st[x] true;if (dfs(depth 1)) return true;st[x] false;}return false;}}return true;}void run() {Scanner sc new Scanner(System.in);int T sc.nextInt();while (T-- 0) {n sc.nextInt();idx 0;Arrays.fill(st, false);for (int len 1; len n; len) {for (int r 0; r len n; r) {for (int c 0; c len n; c) {add(r, c, len);}}}int k sc.nextInt();while (k-- 0) {int x sc.nextInt();st[x] true;}maxDepth 0;while (!dfs(0)) maxDepth;System.out.println(maxDepth);}sc.close();}
} 题目描述给定一个(9*9)的数独矩阵这个矩阵每个位置都有一个得分。从中心向四周扩展每向前一步就减1。现在要将数独填满求最高的得分和是多少 数据规模 n 9 **分析**数独问题我们可以用深搜来做对于要求最高的得分我们可以在搜索时增加一个属性当前层的得分我们要在所有满足边界条件时求最大的得分。 优化 搜索顺序我们优先将可选项最少的位置开始填。 题解: 我们先将row、col、cell预处理代表所有数都可选的状态。然后预处理出0 ~ 2^9 - 1这些二进制数将它们二进制下对应1的个数存入ones中。将每个位置的分数预处理存入score中。根据输入的情况填标记数组g和row、col、cell将当前已选的数标记为0并求当前的分数累计之和求未填项的个数。进行搜索每次扫描标记数组g看哪个位置可选项最少就从该位置开始搜索。满足边界条件时更新当前ans TIPS无 时间复杂度O(n^81) #includeiostream
#includealgorithm
using namespace std;const int N 9, INF 10;
int row[N], col[N], cell[N];
int ones[1 N], log_arr[1 N];
int score[N * N];
char g[N][N];
int ans -1;
/*** 获取二进制最低位1* param x* return*/
inline int lowbit(int x){return x -x;
}
/*** 初始化二进制数组和得分*/
void init(){for(int i 0; i N; i) {row[i] (1 N) - 1;col[i] (1 N) - 1;cell[i] (1 N) - 1;}for(int i 0; i 1 N; i){for(int j i; j; j - lowbit(j)){ones[i];}}for(int i 0; i N; i) {log_arr[1 i] i;}for(int i 0; i N; i){for(int j 0; j N; j){int idx i * N j;score[idx] min(min(i, N - 1 - i), min(j, N - 1 - j)) 6;}}
}
/*** 获取当前可选项* param x* param y* return*/
int get(int x, int y){return row[x] col[y] cell[x / 3 * 3 y / 3];
}
/*** 更改二进制数组和字符阵列* param x* param y* param t*/
void draw(int x, int y, int t){if(t 0){//填数row[x] - 1 (t - 1);col[y] - 1 (t - 1);cell[x / 3 * 3 y / 3] - 1 (t - 1);g[x][y] (char)(0 t);}else if(t 0){g[x][y] 0;}else {//不填数清空t -t;row[x] 1 (t - 1);col[y] 1 (t - 1);cell[x / 3 * 3 y / 3] 1 (t - 1);g[x][y] 0;}
}/*** 获取得分* param x* param y* param t* return*/
int get_score(int x, int y, int t){return score[x * N y] * t;
}
/*** 深度优先搜索* param cnt* param score*/
void dfs(int cnt, int sum){if(!cnt) {ans max(ans, sum);return;}//剪枝int x, y, min INF;//扫描字符阵列for(int i 0; i N; i){for(int j 0; j N; j){//若当前位置没填的话就看看当前位置有多少可选项if(g[i][j] 0){int t ones[get(i, j)];//若当前可选项个数小于min就将min更新为t将x、y更新为i,jif(t min) {min t;x i, y j;}}}}//获取每个位置的1并看这个1是第几位即是那个数for(int i get(x, y); i; i - lowbit(i)){int t log_arr[lowbit(i)] 1;//将当前数填上draw(x, y, t);//继续向下搜索dfs(cnt - 1, sum get_score(x, y, t));//撤销当前操作draw(x, y, -t);}
}int main(){init();int cnt 0, sum 0;for(int i 0; i N; i){for(int j 0; j N; j){char t[2];cin t;int num t[0] - 0;draw(i, j, num);if(num)sum get_score(i, j, num);else cnt;}}dfs(cnt, sum);cout ans endl;return 0;
}import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 9, INF 10;int[] row new int[N], col new int[N], cell new int[N];int[] ones new int[1 N], log new int[1 N];int[] score new int[N * N];int[][] g new int[N][N];int ans -1;void init(){for(int i 0; i N; i){row[i] (1 N) - 1;col[i] (1 N) - 1;cell[i] (1 N) - 1;}for(int i 0; i 1 N; i){for(int j i; j 0; j - lowbit(j)){ones[i];}}for(int i 0; i N; i) log[1 i] i;for(int i 0; i N; i){for(int j 0; j N; j){int idx i * N j;score[idx] Math.min(Math.min(i, N - 1 - i), Math.min(j, N - j - 1)) 6;}}}void draw(int x, int y, int t){if(t 0){row[x] - 1 (t - 1);col[y] - 1 (t - 1);cell[x / 3 * 3 y / 3] - 1 (t - 1);g[x][y] t;}else if(t 0){g[x][y] 0;}else{t -t;row[x] 1 (t - 1);col[y] 1 (t - 1);cell[x / 3 * 3 y / 3] 1 (t - 1);g[x][y] 0;}}int getScore(int x, int y, int t){return score[x * N y] * t;}int get(int x, int y){return row[x] col[y] cell[x / 3 * 3 y / 3];}void dfs(int cnt, int sum){if(cnt 0){ans Math.max(ans, sum);return;}int x 0, y 0, min INF;for(int i 0; i N; i){for(int j 0; j N; j){if(g[i][j] 0){int t ones[get(i, j)];if(t min){min t;x i;y j;}}}}for(int i get(x, y); i 0; i - lowbit(i)){int t log[lowbit(i)] 1;draw(x, y, t);dfs(cnt - 1, sum getScore(x, y, t));draw(x, y, -t);}}int lowbit(int x){return x -x;}void run(){Scanner sc new Scanner(System.in);init();int cnt 0, sum 0;for(int i 0; i N; i){for(int j 0; j N; j){int t sc.nextInt();draw(i, j, t);if(t 0) sum getScore(i, j, t);else cnt;}}dfs(cnt, sum);System.out.println(ans);sc.close();}
}题目描述给定一个算式及进制求算式中各个字母分别代表的数字是多少 数据规模 N 26 **分析**这里显然要使用深搜来做重点是如何优化。 优化 从右到左的顺序来枚举每个字母所代表的数字。若后面所有字母都是确定的则可以直接判断每一位是否合法若后面某些字母没有确定则有两种情况。1.进位是0(A B 0) % N c 2.进位是1(A B 1) % N c最高位不能有进位。 题解: 先将输入按从右到左从上到下的顺序将字母按第一次出现的编号加入q中方便在dfs时按这个顺序赋值与计算。搜索-dfs()这里我们先看当前数是否已经使用过若没有就标记并尝试将path中q对应的该位置赋为该值每次向下搜索时先进行剪枝操作。剪枝-check(),同样是按从右到左的顺序分别获取b、c、d看当前位置是否已经赋值若赋过值就先看余数是否存在若存在就看当前式子是否合法并更新r。若不存在就按余数为0或余数为1对当前式子进行合法性判断。若当前式子未赋值就标记余数为-1.输出path TIPS无 时间复杂度O(26!*26) #includeiostream
#includecstringusing namespace std;
const int N 30;
int n;
char e[3][N];//存数组
int q[N], path[N];//存序列号、存答案
bool st[N];//表示当前字符是否访问过
bool check(){for(int i n - 1, t 0; i 0; i--){int a e[0][i] - A, b e[1][i] - A, c e[2][i] - A;if(path[a] ! -1 path[b] ! -1 path[c] ! -1){//若这三位数都确定下来了a path[a], b path[b], c path[c];if(t ! -1){//若前式确定下来了存在余数if((a b t) % n ! c) return false;//若当前组合不合法返回falseif(!i a b t n) return false;//若最高位还有余数返回falset (a b t) / n;}else{//若不存在与余数if((a b 0) % n ! c (a b 1) % n ! c) return false;if(!i a b n) return false;}}else t -1;}return true;
}bool dfs(int u){//边界条件if(u n) return true;for(int i 0; i n; i){if(!st[i]){//若该数没填就填它st[i] true;path[q[u]] i;if(check() dfs(u 1)) return true;st[i] false;path[q[u]] -1;}}return false;
}
int main(){scanf(%d, n);for(int i 0; i 3; i) {scanf(%s, e[i]);}//从右到左从上到下k用来维护当前字符的编号for(int i n - 1, k 0; i 0; i--){for(int j 0; j 3; j){int t e[j][i] - A;if(!st[t]){st[t] true;q[k] t;}}}memset(st, false, sizeof st);memset(path, -1, sizeof path);dfs(0);for(int i 0; i n; i) printf(%d , path[i]);return 0;
}import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 30;char[][] a new char[3][];int[] q new int[N], path new int[N];boolean[] st new boolean[N];int n;boolean check(){for(int i n - 1, r 0; i 0; i--){int b a[0][i] - A, c a[1][i] - A, d a[2][i] - A;if(path[b] ! -1 path[c] ! -1 path[d] ! -1){b path[b];c path[c];d path[d];if(r ! -1){if((b c r) % n ! d) return false;if(i 0 b c r n) return false;r (b c r) / n;}else{if((b c 0) % n ! d (b c 1) % n ! d) return false;if(i 0 (b c) n) return false;}}else r -1;}return true;}boolean dfs(int u){if(u n) return true;for(int i 0; i n; i) {if(!st[i]){st[i] true;path[q[u]] i;if(check() dfs(u 1)) return true;st[i] false;path[q[u]] -1;}}return false;}void run(){Scanner sc new Scanner(System.in);n sc.nextInt();for (int i 0; i 3; i) {a[i] sc.next().toCharArray();}for(int i n - 1, k 0; i 0; i--){for(int j 0; j 3; j){int t a[j][i] - A;if(!st[t]){st[t] true;q[k] t;}}}Arrays.fill(path, -1);Arrays.fill(st, false);dfs(0);for(int i 0; i n; i) System.out.printf(%d , path[i]);sc.close();}
}题目描述给定一个7*5列的棋盘里面有很多种颜色的方块。相邻的两个方块可以左右交换位置方块不允许悬空。当同一行或同一列有三个或三个以上方块是相邻的这三个方块会同时消失。注意一个方块可以同时属于一行或一列也就是说当行和列同时满足时这些方块会同时消失。若能正好在n次交换后使得棋盘中的全部方块消失就输出对应方块执行的交换操作这里有多组测试数据时要求输出字典序最小的一组解。若没有解决方案则输出-1 数据规模 0 n 5 **分析**该题是带有搜索的模拟题可以用深搜来做。 优化 每一步一次枚举操作哪个格子再枚举向哪个方向移动。若某种颜色只有1个或两个小方块则直接回溯。枚举向左移动时如果左边有方块则直接回溯。我们只考虑向右边移动。 题解: 见分析 TIPS无 时间复杂度O((nm)^5) #includeiostream
#includecstring
#includealgorithmusing namespace std;
const int N 5, M 7;
int n;
int g[N][M], bg[N][N][M];
int cnt[11], bcnt[N][11];
bool st[N][M];struct Point{int x, y, d;
}path[5];void move(int a, int b, int c){swap(g[a][b], g[c][b]);while(true){bool flag true;//处理悬空格for(int x 0; x N; x){int z 0;for(int y 0; y M; y){if(g[x][y])g[x][z] g[x][y];}while(z M) g[x][z] 0;}memset(st, false, sizeof st);//枚举左右上下对可以删除的格子进行标记for(int x 0; x N; x){for(int y 0; y M; y){if(g[x][y]){//横向int l x, r x;while(l - 1 0 g[l - 1][y] g[x][y]) l--;while(r 1 N g[r 1][y] g[x][y]) r;if(r - l 1 3){st[x][y] true;flag false;}//纵向l r y;while(l - 1 0 g[x][l - 1] g[x][y]) l--;while(r 1 M g[x][r 1] g[x][y]) r;if(r - l 1 3){st[x][y] true;flag false;}}}}if(flag) break;//对标记的单元格进行删除for(int x 0; x N; x){for(int y 0; y M; y){if(st[x][y]){cnt[0]--;cnt[g[x][y]]--;g[x][y] 0;}}}}
}bool dfs(int u){if(u n) return !cnt[0];//边界条件当执行第n个操作且当前图中没有方块//第一次剪枝for(int i 1; i 10; i)if(cnt[i] 1 || cnt[i] 2) return false;//枚举所有操作memcpy(bg[u], g, sizeof g);memcpy(bcnt[u], cnt, sizeof cnt);for(int x 0; x N; x){for(int y 0; y M; y){if(g[x][y]){int nx x 1;if(nx N){path[u] {x, y, 1};move(x, y, nx);if(dfs(u 1)) return true;//回溯memcpy(g, bg[u], sizeof g);memcpy(cnt, bcnt[u], sizeof cnt);}//第二次剪枝nx x - 1;if(nx 0 !g[nx][y]){path[u] {x, y, -1};move(x, y, nx);if(dfs(u 1)) return true;memcpy(g, bg[u], sizeof g);memcpy(cnt, bcnt[u], sizeof cnt);}}}}return false;
}int main(){scanf(%d, n);//枚举每一列for(int x 0; x N; x){int t, y 0;//当该行值不为0时就分别对总方块个数、当前颜色个数进行计数图进行赋值while(scanf(%d, t), t){cnt[0];cnt[t];g[x][y] t;}}if(dfs(0)){for(int i 0; i n; i) printf(%d %d %d\n, path[i].x, path[i].y, path[i].d);}else puts(-1);return 0;
}import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}class Block{int x, y, d;public Block(int x, int y, int d) {this.x x;this.y y;this.d d;}}final int N 5, M 7;int[][] g new int[N][M];int[] cnt new int[11];boolean[][] st new boolean[N][M];int[][][] bg new int[N][N][M];int[][] bcnt new int[N][11];Block[] path new Block[N];int n;void move(int a, int b, int c){int t g[a][b];g[a][b] g[c][b];g[c][b] t;while(true){boolean flag true;//将空位去除for (int i 0; i N; i) {int k 0;for (int j 0; j M; j) {if(g[i][j] 0){g[i][k] g[i][j];}}while(k M) g[i][k] 0;}//先清除所有标记for (int i 0; i N; i) {Arrays.fill(st[i], false);}//让连续的砖块消失,这里用到了延迟删除for (int i 0; i N; i) {for (int j 0; j M; j) {if(g[i][j] 0){int l i, r i;while(l - 1 0 g[l - 1][j] g[i][j]) l--;while(r 1 N g[r 1][j] g[i][j]) r;if(r - l 1 3) {st[i][j] true;flag false;}l r j;while(l - 1 0 g[i][l - 1] g[i][j]) l--;while(r 1 M g[i][r 1] g[i][j]) r;if(r - l 1 3) {st[i][j] true;flag false;}}}}//若没有要更新的if(flag) break;for(int i 0; i N; i)for(int j 0; j M; j)if(st[i][j]){cnt[0]--;cnt[g[i][j]]--;g[i][j] 0;}}}boolean dfs(int u){if(u n) return cnt[0] 0;//第一次剪枝for (int i 1; i 10; i)if(cnt[i] 1 || cnt[i] 2) return false;for(int i 0; i N; i){System.arraycopy(g[i], 0, bg[u][i], 0, M);}System.arraycopy(cnt, 0, bcnt[u], 0, 11);for (int i 0; i N; i) {for (int j 0; j M; j) {if(g[i][j] 0){int nx i 1;if(nx N){path[u] new Block(i, j, 1);move(i, j, nx);if(dfs(u 1)) return true;for(int k 0; k N; k){System.arraycopy(bg[u][k], 0, g[k], 0, M);}System.arraycopy(bcnt[u], 0, cnt, 0, 11);}nx i - 1;if(nx 0 g[nx][j] 0){path[u] new Block(i, j, -1);move(i, j, nx);if(dfs(u 1)) return true;for(int k 0; k N; k){System.arraycopy(bg[u][k], 0, g[k], 0, M);}System.arraycopy(bcnt[u], 0, cnt, 0, 11);}}}}return false;}void run(){Scanner sc new Scanner(System.in);n sc.nextInt();for (int i 0; i N; i) {int j 0, t;while(true){t sc.nextInt();if(t 0) break;cnt[0];cnt[t];g[i][j] t;}}sc.close();if(dfs(0)){for(int i 0; i n; i) System.out.printf(%d %d %d\n, path[i].x, path[i].y, path[i].d);}else System.out.println(-1);}
} 题目描述一个男子在 12:00 到达某车站并在 12:00 ~ 12:59 期间在那里逗留。已给出巴士抵达的时间求下列所有巴士在满足到达本站输入数据的情况下求总路线最少是多少 数据规模 n 60 **分析**我们可以先预处理出所有可能的线路。先枚举起点i再枚举公差j。i 和 j需要满足两个条件 因为 i 是起点因此 0 ~ i - 1中不能包含任何该序列的点公差至少从i 1开始 因为 0 ~ 59 之间至少要包含两个点 因此 i j 60 问题就转化为至少从合法线路中选出多少条才可以覆盖所有给定的公交车。这里答案比较浅。因此可以采用迭代加深来搜索。 优化 因为是枚举组合数并不是排列数为了避免重复在枚举时传入当前起点start将所有等差序列按长度排序优先枚举长度较长的等差数列。这样在搜索树中前几层分支较少可以快速的发现矛盾并回溯。由于优化2的存在当前路线覆盖的点数是最多的。若当前路线覆盖的点数 * 剩余可选路径条数 当前已选覆盖点数 总点数则说明该方案一定非法直接回溯。 题解: 见分析 TIPS无 时间复杂度O( C C 60 2 17 C_{C_{60}^{2}}^{17} CC60217 ) #includeiostream
#includealgorithm
#includevectorusing namespace std;const int N 2000, M 60;struct Point{int a, b, c;bool operator (const Point b) const{return a b.a;}
};
vectorPoint routes;
int bus[M];//表示第t时刻到站的巴士数量
int n, max_depth;
/*** 检查当前起点和公差是否合法* param a* param d* return*/
bool check(int a, int d){for(int i a; i M; i d){if(!bus[i]) return false;}return true;
}bool dfs(int depth, int sum, int start){if(depth max_depth) return sum n;if(routes[start].a * (max_depth - depth) sum n) return false;for(int i start; i routes.size(); i){auto r routes[i];int a r.b, d r.c;if(!check(a, d)) continue;for(int j a; j 60; j d) bus[j]--;if(dfs(depth 1, sum r.a, i)) return true;for(int j a; j 60; j d) bus[j];}return false;
}int main(){scanf(%d, n);for(int i 0; i n; i){int t;scanf(%d, t);bus[t];}//预处理for(int i 0; i M; i){for(int j i 1; i j M; j){if(check(i, j)) routes.push_back({(M - 1 - i) / j 1, i, j});//当前路径车的数量}}sort(routes.begin(), routes.end());max_depth 0;while(!dfs(0, 0, 0)) max_depth;printf(%d\n, max_depth);return 0;
}import java.util.*;public class Main {public static void main(String[] args) {new Main().run();}int N 2000, M 60;class Point{int a, b, c;public Point(int a, int b, int c) {this.a a;this.b b;this.c c;}Overridepublic String toString() {return Point{ a a , b b , c c };}}ListPoint routes new ArrayList();int[] bus new int[M];int n, maxDepth;boolean check(int a, int d){for(int i a; i M; i d){if(bus[i] 0) return false;}return true;}boolean dfs(int u, int sum, int start){if(u maxDepth) return sum n;if(routes.get(start).a * (maxDepth - u) sum n) return false;for (int i start; i routes.size(); i) {Point t routes.get(i);int a t.b, d t.c;if(!check(a, d)) continue;for(int j a; j M; j d) bus[j]--;if(dfs(u 1, sum t.a, i)) return true;for(int j a; j M; j d) bus[j];}return false;}void run(){Scanner sc new Scanner(System.in);n sc.nextInt();for (int i 0; i n; i) {int t sc.nextInt();bus[t];}for(int i 0; i M; i){for (int j i 1; i j M; j) {if(check(i, j)) routes.add(new Point((M - 1 - i) / j 1, i, j));}}Collections.sort(routes, (o1, o2) - o2.a - o1.a);maxDepth 0;while(!dfs(0, 0, 0)) maxDepth;System.out.println(maxDepth);}
} 题目描述给定一串序列我们想将序列中的元素从左到右依次加入不同的组中使得组中的元素严格单调。现在想知道最少要分多少组? 数据规模 1 n 50 **分析**很显然这是一道搜索题而且问的是最少是多少组因此我们可以用迭代加深来做。 先枚举将该数加到单调递增的序列中还是单调下降的序列中若该数放到单调递增的序列中则枚举将该数放到哪个单调递增的序列后若该数放到单调递减的序列中则枚举将该数放到哪个单调递降的序列后 优化 up[]存储当前所有上升子序列的末尾元素down[]存储当前所有下降子序列的末尾元素基于贪心的思想我们每次枚举最合适的节点插入若该节点也不满足其它节点肯定也不会满足。 题解: 见分析 TIPS无 时间复杂度 O(n*2^n) #includeiostreamusing namespace std;
const int N 60;
int n;
int h[N], up[N], down[N];
int depth;
/**** param u 当前层数* param su 升序序列的个数* param sd 降序序列的个数* return*/
bool dfs(int u, int su, int sd){if(su sd depth) return false;if(u n) return true;//枚举上升序列中的情况bool flag false;for(int i 1; i su; i){if(up[i] h[u]){int t up[i];up[i] h[u];if(dfs(u 1, su, sd)) return true;up[i] t;flag true;break;}}if(!flag){up[su 1] h[u];if(dfs(u 1, su 1, sd)) return true;}//枚举下降子序列中的情况flag false;for(int i 1; i sd; i){if(down[i] h[u]){int t down[i];down[i] h[u];if(dfs(u 1, su, sd)) return true;down[i] t;flag true;break;}}if(!flag){down[sd 1] h[u];if(dfs(u 1, su, sd 1)) return true;}return false;
}
int main(){while(cin n, n){for(int i 0; i n; i) cin h[i];depth 0;while(!dfs(0, 0, 0)) depth;cout depth endl;}return 0;
}import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 60;int[] h new int[N], up new int[N], down new int[N];int depth, n;boolean dfs(int u, int su, int sd){if(su sd depth) return false;if(u n) return true;//枚举上升子序列boolean flag false;for (int i 1; i su; i) {if(up[i] h[u]){int t up[i];up[i] h[u];flag true;if(dfs(u 1, su, sd)) return true;up[i] t;break;}}if(!flag){up[su 1] h[u];if(dfs(u 1, su 1, sd)) return true;}//枚举下降子序列flag false;for(int i 1; i sd; i){if(down[i] h[u]){int t down[i];down[i] h[u];flag true;if(dfs(u 1, su, sd)) return true;down[i] t;break;}}if(!flag){down[sd 1] h[u];if(dfs(u 1, su, sd 1)) return true;}return false;}void run(){Scanner sc new Scanner(System.in);while(true){n sc.nextInt();if(n 0) break;for (int i 0; i n; i) h[i] sc.nextInt();depth 0;while(!dfs(0, 0, 0)) depth;System.out.println(depth);}sc.close();}
} 题目描述给定一个地图以及起点和终点。地图中有墙和可以移动的区域。人从起始位置开始可以以日字形跳跃。每次跳跃步数1。现在想知道从起点到终点至少需要多少步。 数据规模 1 n 150 **分析**很显然这里可以用宽搜来做基于dijkstra算法的思想。 **优化**无 题解: 见分析 TIPS这里跳跃时可以向八个方向跳跃。 时间复杂度 O(n*n) #includeiostream
#includecstring
#includequeue#define x first
#define y second
using namespace std;
typedef pairint, int PII;
const int N 160;
int dist[N][N];
char g[N][N];
int dx[8] {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] {1, 2, 2, 1, -1, -2, -2, -1};
int n, m;int bfs(PII start, PII end){memset(dist, -1, sizeof dist);queuePII q;q.push({start.x, start.y});dist[start.x][start.y] 0;while(q.size()){auto t q.front();q.pop();if(make_pair(t.x, t.y) end) break;for(int i 0; i 8; i){int nx t.x dx[i], ny t.y dy[i];if(nx 0 nx n ny 0 ny m){if(g[nx][ny] *) continue;if(dist[nx][ny] 0) continue;dist[nx][ny] dist[t.x][t.y] 1;q.push({nx, ny});}}}return dist[end.x][end.y];
}
int main(){cin m n;for(int i 0; i n; i) cin g[i];PII start, end;for(int i 0; i n; i)for(int j 0; j m; j)if(g[i][j] K) start {i, j};else if(g[i][j] H) end {i, j};cout bfs(start, end) endl;return 0;
}import java.util.*;public class Main {public static void main(String[] args) {new Main().run();}class Pair{int x, y;Overridepublic boolean equals(Object o) {if (this o) return true;if (o null || getClass() ! o.getClass()) return false;Pair pair (Pair) o;return x pair.x y pair.y;}Overridepublic int hashCode() {return Objects.hash(x, y);}public Pair(int x, int y) {this.x x;this.y y;}}final int N 160;char[][] g new char[N][];int[][] dist new int[N][N];int[] dx {-2, -1, 1, 2, 2, 1, -1, -2}, dy {1, 2, 2, 1, -1, -2, -2, -1};int n, m;int bfs(Pair start, Pair end){for (int i 0; i n; i) Arrays.fill(dist[i], -1);QueuePair queue new ArrayDeque();dist[start.x][start.y] 0;queue.offer(new Pair(start.x, start.y));while(!queue.isEmpty()){Pair t queue.poll();int x t.x, y t.y;if(t.equals(end)) break;for (int i 0; i 8; i) {int nx x dx[i], ny y dy[i];if(nx 0 nx n ny 0 ny m){if(g[nx][ny] *) continue;if(dist[nx][ny] ! -1) continue;dist[nx][ny] dist[x][y] 1;queue.offer(new Pair(nx, ny));}}}return dist[end.x][end.y];}void run(){Scanner sc new Scanner(System.in);m sc.nextInt();n sc.nextInt();for(int i 0; i n; i) g[i] sc.next().toCharArray();Pair start new Pair(0, 0), end new Pair(0, 0);for (int i 0; i n; i) {for (int j 0; j m; j) {if(g[i][j] K) start new Pair(i, j);else if(g[i][j] H) end new Pair(i, j);}}sc.close();System.out.println(bfs(start, end));}
} 题目描述给定两个字符串以及若干规则问能否通过这些规则在十步之内将字符1转换为字符2?若可以输出步数否则输出-1 数据规模 1 n 10 1 l 20 **分析**我们可以将字符串抽象成图若对应的字符字串能转换为另外一个字串则这两个字串之间存在权值为1的边。由于这里是求步数最少因此我们可以使用广度优先算法,由于状态空间很大这里采用双向bfs搜索。 **优化**无 题解: 见分析 TIPS这里需要逐层搜索然后判断。 时间复杂度 O((l*n)^5) #includeiostream
#includequeue
#includeunordered_mapusing namespace std;const int N 6;
int n;
string A, B;
string a[N], b[N];int extend(queuestring q, unordered_mapstring, int da, unordered_mapstring, int db, string a[N], string b[N]){int d da[q.front()];while(q.size() da[q.front()] d){auto t q.front();q.pop();for(int i 0; i n; i)for(int j 0; j t.size(); j)if(t.substr(j, a[i].size()) a[i]){string r t.substr(0, j) b[i] t.substr(j a[i].size());if(db.count(r)) return da[t] db[r] 1;if(da.count(r)) continue;da[r] da[t] 1;q.push(r);}}return 11;
}
int bfs(){if(A B) return 0;queuestring qa, qb;unordered_mapstring, int da, db;qa.push(A), qb.push(B);da[A] db[B] 0;int step 0;while(qa.size() qb.size()){int t;if(qa.size() qb.size()) t extend(qa, da, db, a, b);else t extend(qb, db, da, b, a);if(t 10) return t;if(step 10) return -1;}return -1;
}
int main(){cin A B;while (cin a[n] b[n]) n ;int t bfs();if(t -1) puts(NO ANSWER!);else cout t endl;return 0;
} import java.util.*;public class Main {public static void main(String[] args) {new Main().run();}final int N 8;int n 0;QueueString qa new ArrayDeque(), qb new ArrayDeque();//两个队列MapString, Integer ma new HashMap(), mb new HashMap();//存从a到中见状态所需要的步数存b到中间状态需要的步数。String[] a new String[N], b new String[N];//对应规则String A, B;/*** 从a到b进行扩展* param q 队列* param ma * param mb* param a* param b* return*/int extend(QueueString q, MapString, Integer ma, MapString, Integer mb, String[] a, String[] b){int d ma.get(q.peek());for(int k 0, len q.size(); k len; k){String t q.poll();for(int i 0; i t.length(); i){for(int j 0; j n; j){//我们首先看当前t中是否含有a中的字符串if(i a[j].length() t.length() t.substring(i, i a[j].length()).equals(a[j])){String r t.substring(0, i) b[j] t.substring(i a[j].length());if(mb.containsKey(r)) return ma.get(t) mb.get(r) 1;if(ma.containsKey(r)) continue;ma.put(r, ma.get(t) 1);//步数 1q.offer(r);}}}}return 11;}int bfs(){if(A.equals(B)) return 0;qa.offer(A);qb.offer(B);ma.put(A, 0);mb.put(B, 0);int step 0;while(!qa.isEmpty() !qb.isEmpty()){int t 0;//若qa比较小我们就更新它if(qa.size() qb.size()) t extend(qa, ma, mb, a, b);else t extend(qb, mb, ma, b, a);if(t 10) return t;if(step 10) return -1;}return -1;}void run(){Scanner sc new Scanner(System.in);A sc.next();B sc.next();while(sc.hasNext()){a[n] sc.next();b[n] sc.next();}sc.close();int ans bfs();if(ans -1) System.out.println(NO ANSWER!);else System.out.println(ans);}
} 题目描述给定一个5*5的棋盘最终的位置应该是这样左下角是白子右上角是黑子。现在棋子可以通过跳日子形到空位上问至少需要调多少次才能使得所有棋子归为?(步数不超过15) 数据规模 n 5 **分析**这里显然是一道搜索题且最终的步数不会超过15步因此我们可以考虑使用迭代加深进行搜索。 优化 我们可以加上一个估价函数进行剪枝。可以这样设计将当前棋子中有多少个棋子未归为作为估价函数。满足当前步数 估价函数 真实值 题解: 见分析 TIPSIDA* 时间复杂度 O(8^15) #includeiostreamusing namespace std;
const int N 5;
int g[N][N];
int dest[N][N] {{-1, -1, -1, -1, -1},{1, -1, -1, -1, -1},{1, 1, 0, -1, -1},{1, 1, 1, 1, -1},{1, 1, 1, 1, 1}
};
int dx[8] {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] {1, 2, 2, 1, -1, -2, -2, -1};
int n, depth;
/*** 估价函数还有多少棋子未归位* return*/
int f(){int cnt 0;for(int i 0; i N; i)for(int j 0; j N; j)if(g[i][j] g[i][j] ! dest[i][j]) cnt;return cnt;
}
bool dfs(int u, int x, int y){if(u f() depth) return false;if(!f()) return true;for(int i 0; i 8; i){int nx x dx[i], ny y dy[i];if(nx 0 || nx N || ny 0 || ny N) continue;swap(g[x][y], g[nx][ny]);if(dfs(u 1, nx, ny)) return true;swap(g[x][y], g[nx][ny]);}return false;
}
int main(){cin n;while(n--){int x, y;for(int i 0; i N; i){char s[5];scanf(%s, s);for(int j 0; j N; j){if(s[j] 1) g[i][j] -1;else if(s[j] *) {g[i][j] 0;x i, y j;}else g[i][j] 1;}}depth 0;while(depth 15 !dfs(0, x, y)) depth;if(depth 15) puts(-1);else cout depth endl;}
}import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final int N 5;int[][] g new int[N][N];int[][] dest {{-1, -1, -1, -1, -1},{1, -1, -1, -1, -1},{1, 1, 0, -1, -1},{1, 1, 1, 1, -1},{1, 1, 1, 1, 1}};int[] dx {-2, -1, 1, 2, 2, 1, -1, -2};int[] dy {1, 2, 2, 1, -1, -2, -2, -1};int n, depth;/*** 股价函数* return*/int f(){int cnt 0;for(int i 0; i N; i)for(int j 0; j N; j)if(g[i][j] ! 0 g[i][j] ! dest[i][j]) cnt;return cnt;}boolean dfs(int u, int x, int y){if(u f() depth) return false;if(f() 0) return true;for(int i 0; i 8; i){int nx x dx[i], ny y dy[i];if(nx 0 || nx N || ny 0 || ny N) continue;g[x][y] g[nx][ny];g[nx][ny] 0;if(dfs(u 1, nx, ny)) return true;g[nx][ny] g[x][y];g[x][y] 0;}return false;}void run(){Scanner sc new Scanner(System.in);n sc.nextInt();while(n-- 0){int x 0, y 0;for(int i 0; i N; i){char[] line sc.next().toCharArray();for(int j 0; j N; j){if(line[j] 1) g[i][j] -1;else if(line[j] 0) g[i][j] 1;else {x i;y j;}}}depth 0;while(!dfs(0, x, y) depth 15) depth;if(depth 15) System.out.println(depth);else System.out.println(-1);}sc.close();}
}
