上海cms模板建站,网站的根目录,建购物网站多少钱,网站建设基本流程包括以下是广搜水题
题意#xff1a;输入一个n*n的迷宫#xff0c;输入从起点到终点的最短路
输入#xff1a;
12 //迷宫大小 2 9 11 8 //起点和终点 1 1 1 1 1 1 1 1 1 1 1 1 //邻接矩阵#xff0c;0表示通#xff0c;1表示不通 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 1 0 …以下是广搜水题
题意输入一个n*n的迷宫输入从起点到终点的最短路
输入
12 //迷宫大小 2 9 11 8 //起点和终点 1 1 1 1 1 1 1 1 1 1 1 1 //邻接矩阵0表示通1表示不通 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输出
(2,9)-(3,9)-(3,8)-(3,7)-(4,7)-(5,7)-(5,6)-(5,5)-(5,4)-(6,4)-(7,4)-(7,3)-(7,2)-(8,2)-(9,2)-(9,3)-(9,4)-(9,5)-(9,6)-(8,6)-(8,7)-(8,8)-(9,8)-(9,9)-(10,9)-(11,9)-(11,8) 27 代码 #includecstdio
using namespace std;
int dwax[4]{0,0,1,-1},dway[4]{1,-1,0,0};
int n,m,state[2501][2],father[2501],px,py,x,y,head,tail,s;
bool a[51][51];
void write(int x,int dep)
{
if (x0) return;//如果到x则0则为返回完毕
s;
write(father[x],dep1);//返回
printf((%d,%d),state[x][0],state[x][1]);//输出路径
if (dep!0) printf(-);
}
void bfs()
{
head0;//预处理
tail1;
do
{
head1;//出队
xstate[head][0];
ystate[head][1];
for (int i0;i4;i) if (!a[xdwax[i]][ydway[i]] xdwax[i]n ydway[i]n xdwax[i]1 ydway[i]1)//判断是否可以通行{tail;//入队father[tail]head;state[tail][0]xdwax[i];state[tail][1]ydway[i];a[xdwax[i]][ydway[i]]true;//封路if (xdwax[i]px ydway[i]py)//判断终点{write(tail,0);return;}} }while (headtail);//如果队列空了则退出}
int main()
{scanf(%d%d%d%d%d,n,x,y,px,py);int q0;for (int i1;in;i)for (int j1;jn;j){scanf(%d,q);if (q1) a[i][j]true;}//以上为输入不解释state[1][0]x;state[1][1]y;a[x][y]true;bfs();printf(\n%d,s);
}题目2骑士旅行
在一个n m 格子的棋盘上有一只国际象棋的骑士在棋盘的左下角 (1;1)(如图1)骑士只能根据象棋的规则进行移动要么横向跳动一格纵向跳动两格要么纵向跳动一格横向跳动两格。 例如 n4m3 时若骑士在格子(2;1) (如图2), 则骑士只能移入下面格子(1;3),(3;3) 或 (4;2)对于给定正整数nmIj值 (m,n50,In,jm) 你要测算出从初始位置(1;1) 到格子(i;j)最少需要多少次移动。如果不可能到达目标位置则输出NEVER。 输入
5 3
1 2
输出
3 代码 #includecstdio
using namespace std;
int dwax[8]{1,1,-1,-1,2,2,-2,-2},dway[8]{2,-2,2,-2,1,-1,1,-1};
int n,m,state[2501][3],father[2501],px,py,x,y,head,tail,s;
bool a[51][51];
void write(int x)//检测bug的攻击
{if (x0) return;s;write(father[x]);printf([%d , %d]-[%d , %d]\n,state[father[x]][0],state[father[x]][1],state[x][0],state[x][1]);//输出路径
}
void bfs()
{head0;//初始化不解释tail1;do{head1;//出队xstate[head][0];ystate[head][1];for (int i0;i8;i) if (!a[xdwax[i]][ydway[i]] xdwax[i]n ydway[i]m xdwax[i]1 ydway[i]1)//判断可否通行{tail;father[tail]head;state[tail][0]xdwax[i];state[tail][1]ydway[i];state[tail][2]state[head][2]1;a[xdwax[i]][ydway[i]]true;//封路if (xdwax[i]px ydway[i]py){//write(tail);sstate[tail][2];return;}} }while (headtail);//空队列结束广搜
}
int main()
{scanf(%d%d%d%d,m,n,px,py);state[1][0]1;state[1][1]1;state[1][2]1;a[1][1]true;//输入初始化不解释bfs();if (headtail) printf(NEVER);else printf(%d,s-1);//输出不解释
}题目3翻币问题
有N个硬币(6N20000)全部正面朝上排成一排每次将其中5个硬币翻过来放在原位置直到最后全部硬币翻成反面朝上为止。试编程找出步数最少的翻法输出最少步数及翻法。 输入
6
输出
6 代码 #includecstdio
using namespace std;
int state[20001],father[20001],head,tail,s,n;
bool ok[20001];
void print(int x)//返回输出
{if (x0) return;print(father[x]);//printf(%d:%d\n,s,state[x]);s;
}
void bfs()
{state[1]n;head0;tail1;do{head;//出队for (int i0;i5;i)//翻得硬币正面个数if (state[head]i n-state[head]5-i)//如果正面和反面数量足够{tail;//入队father[tail]head;//记录父节点state[tail]state[head]-i5-i;//翻if (ok[state[tail]])//判断有没有重复{tail--;continue;}ok[state[tail]]true;//封if (state[tail]0)//判断结束{print(tail);return;}}}while (headtail);//结束队列
}
int main()
{scanf(%d,n);bfs();printf(%d,s-1);//输出
}题目4最优乘车H城是一个旅游胜地每年都有成千上万的人前来观光。为方便游客巴士公司在各个旅游景点及宾馆饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发依次途经若干个巴士站最终到达终点巴士站。 一名旅客最近到H城旅游他很想去S公园游玩但如果从他所在的饭店没有一路已士可以直接到达S公园则他可能要先乘某一路巴士坐几站再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。 现在用整数1,2,…N 给H城的所有的巴士站编号约定这名旅客所在饭店的巴士站编号为1…S公园巴士站的编号为N。 写一个程序帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。 题目很烦是吧 输入
3 7 6 7 4 7 3 6 2 1 3 5
输出
2 代码 #includecstdio
using namespace std;
int a,k,bus[101][101],num[101][101],state[10001][3],head,tail,s,n,m;
char c;
bool ok[101];
void bfs()
{head0;tail1;state[1][0]0;state[1][1]1;state[1][2]0;//初始化不解释do{head;for (int i1;inum[state[head][1]][0];i)//枚举当前站可以到达的站{if (ok[num[state[head][1]][i]]) continue;//去重ok[num[state[head][1]][i]]true;//封tail;state[tail][1]num[state[head][1]][i];state[tail][0]state[head][0]1;//状态读入if (state[tail][1]n)//判断结束{sstate[tail][0];return;}}}while(headtail);
}
int main()
{scanf(%d%d,m,n);scanf(\n);for (int i1;im;i){while ((cgetchar())!\n){if (c! ) aa*10c-48;//读取数字else {k;bus[i][k]a;//记录该公交线for (int j1;jk;j) {num[bus[i][j]][0];num[bus[i][j]][num[bus[i][j]][0]]a;//记录该点可以到达哪站}a0;}}k;bus[i][k]a;for (int j1;jk;j) {num[bus[i][j]][0];num[bus[i][j]][num[bus[i][j]][0]]a;}//最后一个的处理a0;bus[i][0]k;k0;}//以上为预处理bfs();if (s0) printf(NO);else printf(%d,s-1);
}好了初见题就那么多。
