网站的关于我们怎么做,厦门域名空间建网站,网站用自己的电脑做服务器吗,软件公司经营范围几道例题还比较简单#xff0c;练习就卡了比较长的时间了(。_。)
所以我会写一下解题思路了(๑ŐдŐ) 还有博客抽风所以代码里会有一些奇奇怪怪的东西#xff0c;无视就好了qwq。
这几道题我就按各人认为的难易程度来排序吧QAQ。
第一题.
题意#xff1a;输入一个迷宫练习就卡了比较长的时间了(。_。)
所以我会写一下解题思路了(๑ŐдŐ) 还有博客抽风所以代码里会有一些奇奇怪怪的东西无视就好了qwq。
这几道题我就按各人认为的难易程度来排序吧QAQ。
第一题.
题意输入一个迷宫输出起点到终点的最短路径。 输入
10 0100110100 0001110010 1000000001 1000100011 0000101100 1000001100 1001010011 0000010100 0101010000 1001000001 1 7 10 2
输出
14 解题思路就是走迷宫233。之前做过的了(⊙o⊙)。
详见http://blog.csdn.net/mr_wuyongcong/article/details/78732439 广搜例题 代码 #includecstdio
using namespace std;
int n,head,tail,state[1000001][3],x,y,s,py,px;
bool walk[1001][1001];
int dx[4]{0,0,1,-1},dy[4]{1,-1,0,0};//移动方式
char c;
void bfs()
{state[1][2]0;head0;tail1;do{head;//出队for (int i0;i4;i){xstate[head][0]dx[i];//位置ystate[head][1]dy[i];//位置if (walk[x][y] x0 y0 xn yn)//是否可以通行{tail;//入队state[tail][2]state[head][2]1;state[tail][0]x;state[tail][1]y;walk[x][y]false;//封闭路线if (xpx ypy)//判断终点{sstate[tail][2];return;}}}}while(headtail);//判断结束
}
int main()
{scanf(%d\n,n);for (int i1;in;i){for (int j1;jn;j){cgetchar();if (c0) walk[i][j]true;}cgetchar();} scanf(%d%d%d%d,state[1][0],state[1][1],px,py); //输入不解释bfs();//广搜不解释printf(%d,s);//输出不解释//就是那么任性QAQ
} 第二题细胞问题水题
题目大意一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。 输入
4 10 0234500067 1034560500 2045600671 0000000089 输出
4 解题思路这道题刚开始做了半天从一个开始搜。后来突然顿悟为什么不能从多个位置开始搜(_)。于是就轻轻松松的搞定了233。 代码 #includecstdio
using namespace std;
int n,m,s,head,tail,state[2401][2];
int dx[4]{0,0,1,-1},dy[4]{1,-1,0,0};//细胞拓展方向
int a[61][61];
char c;
void bfs(int x,int y)
{head0;tail1;state[1][0]x;state[1][1]y;do{head;//出队for (int i0;i4;i){xstate[head][0]dx[i];ystate[head][1]dy[i];if(a[x][y] x0 xm y0 yn)//如果这里是细胞则往这边拓展{tail;//入队a[x][y]false;//封闭该位置细胞state[tail][0]x;state[tail][1]y;}}}while (headtail);
}
int main()
{scanf(%d%d\n,m,n); for (int i1;im;i){for (int j1;jn;j){cgetchar();if (c!0) a[i][j]true;}cgetchar();}//输入不解释 for (int i1;im;i)for (int j1;jn;j)//将所有的细胞枚举一遍{if(a[i][j])//当该处有细胞时数量可以加了{bfs(i,j);//封闭该位置链接的细胞s;//数量加1}}printf(%d,s);//输出
}第三题最小转弯路径难度开始加大了
题意给出一个地图求起点到终点要转的最少弯数。 输入
5 7 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 3 1 7
输出
5
附图 解题思路
最小转弯不是最少步数。做法比较简单不过是把拓展方式从4个方向一个格改成从4个方向撞到墙为止的一次性拓展完。用老师的说法就是代价相同
不过注意封路和墙不要混为一谈。因为他是撞到墙才停止拓展而碰到已经被走过的路只不过是不入队而不是不继续拓展。被卡了好一会qAq 贴代码时间 #includecstdio
using namespace std;
int head,tail,n,m,state[10001][3],c,s,x,y,qx,qy;
bool ok[101][101],a[101][101];
int dx[4]{0,0,1,-1},dy[4]{1,-1,0,0};//拓展方向
void bfs()
{head0;tail1;do{head;//出队for (int i0;i4;i)//4个方向{xstate[head][0];ystate[head][1];int j1;while (!a[xdx[i]*j][ydy[i]*j] xdx[i]*jn ydy[i]*jm xdx[i]*j0 ydy[i]*j0)//如果碰到墙或边缘就结束拓展{if (!ok[xdx[i]*j][ydy[i]*j])//如果已经走过的路线就不入队{tail;//入队state[tail][0]xdx[i]*j;state[tail][1]ydy[i]*j;//储存位置state[tail][2]state[head][2]1;//储存转弯数ok[xdx[i]*j][ydy[i]*j]true;//已经走过该地if (xdx[i]*jqx ydy[i]*jqy)//结束判断{sstate[tail][2];return;}}j;//下一个拓展}}}while(headtail);//空队退出
}
int main()
{scanf(%d%d\n,n,m); for (int i1;in;i){for (int j1;jm;j){scanf(%d,c);if (c!0) a[i][j]true;}}scanf(%d%d%d%d,state[1][0],state[1][1],qx,qy);//输入不解释bfs();//函数不解释printf(%d,s-1);//输出不解释
}最后的压轴题麻将游戏 在一种麻将游戏中游戏是在一个有WH格子的矩形平板上进行的。每个格子可以放置一个麻将牌也可以不放如图所示。玩家的目标是将平板上的所有可通过一条路径相连的两张相同的麻将牌从平板上移去。最后如果能将所有牌移出平板则算过关。 这个游戏中的一个关键问题是两张牌之间是否可以被一条路径所连接该路径满足以下两个特性 1. 它由若干条线段组成每条线段要么是水平方向要么是垂直方向。 2. 这条路径不能横穿任何一个麻将牌 (但允许路径暂时离开平板)。 这是一个例子 在13的牌和在(4, 4)的牌可以被连接。(2, 3)和(3, 4)不能被连接。 你的任务是编一个程序检测两张牌是否能被一条符合以上规定的路径所连接。 输入输入文件的第一行有两个整数wh 1wh75表示平板的宽和高。接下来h行描述平板信息每行包含w个字符如果某格子有一张牌则这个格子上有个X否则是一个空格。平板上最左上角格子的坐标为11最右下角格子的坐标为w,h。接下来的若干行每行有四个数x1 y1 x2 y2 且满足1x1,x2w1y1,y2h表示两张牌的坐标这两张牌的坐标总是不同的。如果出现连续四个0则表示输入结束。
5 4 XXXXX X X XXX X XXX 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0 输出
输出文件中对于每一对牌输出占一行为连接这一对牌的路径最少包含的线段数。如果不存在路径则输出0。
4
3
0 解题思路这道题卡了挺久的近5个小时才做出来。这道题一看就是第三题的升级版只要注意可以走外围和每次把封路还原就Ok了o(﹏)o 终极代码时间 #includecstdio
using namespace std;
int head,tail,state[5930][3],n,m,s,x1,x2,y1,y2;
bool a[77][77],walk[77][77];
int dx[4]{1,-1,0,0},dy[4]{0,0,1,-1};//4个方向
char c;
void bfs(int x,int y,int px,int py)
//计算从(x,y)到(px,py)的最小转弯数
//这里不讲了详见第3题
{head0;tail1;state[1][0]x;state[1][1]y;state[1][2]0;do{head;for (int i0;i4;i){xstate[head][0];ystate[head][1];int j1;while (!a[xdx[i]*j][ydy[i]*j] xdx[i]*jn1 ydy[i]*jm1 xdx[i]*j0 ydy[i]*j0){if (!walk[xdx[i]*j][ydy[i]*j]){tail;state[tail][0]xdx[i]*j;state[tail][1]ydy[i]*j;state[tail][2]state[head][2]1;walk[xdx[i]*j][ydy[i]*j]true;if (xdx[i]*jpx ydy[i]*jpy){sstate[tail][2];return;}}j;}}}while(headtail);
}
int main()
{scanf(%d%d,m,n);//输入注意是反过来的cgetchar();//读第一行的换行符for (int i1;in;i){int j0;while ((cgetchar())!\n){j;if (cX) a[i][j]true;//处理可否通行}} x11;while (x1!0 || y1!0 || x2!0 || y2!0)//如果都为零就退出{scanf(%d%d%d%d,y1,x1,y2,x2);//输入注意是反过来的if (x1!0 y1!0 x2!0 y2!0)//如果都不为0{for (int i0;in1;i)for (int j0;jm1;j) {walk[i][j]false;}//还原封路s0;//还原a[x2][y2]false;//解掉终点的封锁bfs(x1,y1,x2,y2);//求a[x2][y2]true;//打开终点的封锁printf(%d\n,s);}}
}好了广搜题目就那么多。↖(^ω^)↗
