题目 C:
连连看-判断两个图案是否可以消去
时间限制: 10 Sec
内存限制:128 MB
提交: 23
解决: 3
[提交][状态][讨论版]
题目描述
连连看，你不会？那就out了！
给定一个连连看棋盘，棋盘上每个点有各种图案（用非0数字表示），输入棋盘上的任意两个坐标，判断这两个坐标对应的图案是否可以消除，消除的条件是图案相同且图案间连线的转角数不得超过2
。
1 3
3 4
0 6
0 0
4
0 2 1
6
0 4 2
图中，(0,1)和(0,2)中的3没有转角可以消去，(1,1)和(3,0)中的6有一个转角可以消去，(2,0)和(3,2)中的4有两个转角可以消去，而(0,0)和(2，3)中的1不能消去。
输入
输入为连续的整数，第1个数为棋盘行数m，第2个数为棋盘列数n，然后依次是m*n个棋盘数据（先行后列），最后，是两个坐标对应的行号和列号，m行n列的棋盘，共计输入m*n+6个数。
输出
如果图案不能消除，输出0；如果图案可以消除，输出消除路线上图案个数（包含输入的两个图案，不考虑有多条可消除路径的情况）。
样例输入
4,4,1,3,3,4,0,6,0,0,4,0,2,1,6,0,4,2,2,0,3,2
样例输出
4
下面代码还有错误：留着改
#include<iostream>
#include<queue>
using namespace std;
struct Node{
int x;
int y;
int step;
int count;
};
Node sta;
Node fin;
int n=4;
int maze[10][10];
bool vis[10][10];
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int bfs(){
queue<Node> que;
que.push(sta);
while(!que.empty()){
Node t=que.front();
que.pop();
for(int i=0;i<4;++i){
Node next;
next.x=t.x+dir[i][0];
next.y=t.y+dir[i][1];
next.step=t.step+1;
next.count=t.count+1;
if(next.x==fin.x&&next.y==fin.y){
return next.count;
}
if(next.x<=0||next.y>n||next.step>2||maze[next.x][next.y]!=0) continue;
if(vis[next.x][next.y]) continue;
que.push(next);
}
}
return 0;
}
int main(){
int arr[]={1,3,3,4,0,6,0,0,4,0,2,1,6,0,4,2};
int ind=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
maze[i][j]=arr[ind];
ind++;
}
sta.x=2,sta.y=0,sta.step=0,sta.count=1;
fin.x=3,fin.y=2;
cout<<bfs()<<endl;
return 0;
}