青岛手机网站设计公司,织梦教程网,常熟建设合同备案在哪个网站,高端渠道开发题目#xff1a;
“连连看”相信很多人都玩过。没玩过也没关系#xff0c;下面我给大家介绍一下游戏规则#xff1a;在一个棋盘中#xff0c;放了很多的棋子。如果某两个相同的棋子#xff0c;可以通过一条线连起来#xff08;这条线不能经过其它棋子#xff09;#…题目
“连连看”相信很多人都玩过。没玩过也没关系下面我给大家介绍一下游戏规则在一个棋盘中放了很多的棋子。如果某两个相同的棋子可以通过一条线连起来这条线不能经过其它棋子而且线的转折次数不超过两次那么这两个棋子就可以在棋盘上消去。不好意思由于我以前没有玩过连连看咨询了同学的意见连线不能从外面绕过去的但事实上这是错的。现在已经酿成大祸就只能将错就错了连线不能从外围绕过。 玩家鼠标先后点击两块棋子试图将他们消去然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。 Input 输入数据有多组。每组数据的第一行有两个正整数n,m(0 n1000,0 m1000)分别表示棋盘的行数与列数。在接下来的n行中每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子正整数表示棋子的类型。接下来的一行是一个正整数q(0 q50)表示下面有q次询问。在接下来的q行里每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n0,m0时输入结束。 注意询问之间无先后关系都是针对当前状态的 Output 每一组输入数据对应一行输出。如果能消去则输出”YES”,不能则输出”NO”。 Sample Input 3 4 1 2 3 4 0 0 0 0 4 3 2 1 4 1 1 3 4 1 1 2 4 1 1 3 3 2 1 2 4 3 4 0 1 4 3 0 2 4 1 0 0 0 0 2 1 1 2 4 1 3 2 3 0 0 Sample Output YES NO NO NO NO YES
分析与解答
这个题需要考虑转向转向的话就是根据到当前数走的方向与到上个数走的方向是否相同来判断。如果不同转弯的数要加一。现在我们有坐标方向转弯次数就好写了其中我们认为方向0就是向下1向右2向上3向左-1是最初的x1y1的方向意味着从他走向下一个数是不用考虑转弯的只用记录到达这个数的方向 由于他是询问x1y1到x2y2我们只需判断是否有x1y1到x2y2的路这个题让我刷新了对标记数组的认识之前的标记数组都是经过了就变为另一个数下次在经过这个坐标时如果已做过标记就不走。但这个是用于记录从x1y1到ij转弯的最小次数如果在ij这个位置的stepv[i][j],就push到队列里我试了一下如果把这个标志数组去掉就会超时就是从起点到一个点的的路径有多条但是如果只是说经过了就不再考虑到这个点的其他路径的话这个点到终点的转弯次数加上起点到这个点的转弯次数会超过二这是不满足题意的所以我们到这个点之后还需要考虑其他到这个点的路径其唯一目的就是让从起点到终点的路径转弯的次数最小这样的话就有极大的可能从这个路径一直走到终点的过程中转弯的次数满足题意所以我们标记数组只存最小或者等于目前最小的转弯次数的路径 前面还有个判断如果step比2小就继续搜索这是题目要求 还有常规判断走一步之后新的坐标在范围内新坐标这个位置没有棋子这个新坐标就是我们要找的坐标 满足这写条件此时我们再考虑是不是该push了
参考代码 https://blog.csdn.net/jzmzy/article/details/16862263
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define MAXN 1005
using namespace std;
int map[MAXN][MAXN],v[MAXN][MAXN];
const int dx[4] {0,1,0,-1};
const int dy[4] {-1,0,1,0};
int n,m,flag;
struct node
{int x,y;int dir;//记录方向int step;//记录转弯次数
};
int bfs(int x1,int y1,int x2,int y2)
{memset(v,11,sizeof(v));//标志数组 记录某条路径在该点转向的次数queue node q;node s,temp;s.x x1;s.y y1;s.dir -1;//-1表示朝哪个方向都可以s.step 0;q.push(s);while(!q.empty()){temp q.front();q.pop();if(temp.x x2 temp.y y2 temp.step 2)return 1;for(int i 0; i 4; i ){s temp;s.x dx[i];s.y dy[i];//走一步之后新的坐标在范围内而且只有当坐标这个位置没有棋子或者说这个坐标就是我们要找的坐标 if(s.x 1 s.x n s.y 1 s.y m (map[s.x][s.y] 0 || (s.x x2 s.y y2))){if(s.dir ! -1)//s.dir是上上个坐标走到上个坐标的方向这个坐标要从新记录 {if(s.dir ! i)//与上个坐标的方向相反就说明转弯了 {s.dir i;s.step ;}}else s.dir i;//记录走的方向 if(s.step 2) continue;if(s.step v[s.x][s.y])//保证转弯次数最少等号不能忘记{v[s.x][s.y] s.step;q.push(s);}}}}return 0;
}
int main()
{int i,j,t,x1,y1,x2,y2;while(scanf(%d%d,n,m),(nm)){for(i 1; i n; i )for(j 1; j m; j )scanf(%d,map[i][j]);//n行m列的图 scanf(%d,t);while(t--)//从、询问 {scanf(%d%d%d%d,x1,y1,x2,y2);//坐标相同或者数不同或者没有东西 if(!map[x1][y1] || !map[x2][y2] || map[x1][y1] ! map[x2][y2] || (x1 x2 y1 y2) )flag 0;else flag bfs(x1,y1,x2,y2);if(flag) puts(YES);else puts(NO);}}return 0;
}
