sicily 无路可逃?(图的DFS)

题意:在矩阵数组中搜索两点是否可达

解法:DFS

 #include<iostream>
#include<memory.h>
using namespace std;
struct position{
int x;
int y;
position(int xx,int yy){
x = xx;
y = yy;
}
position(){}
}; int maze[][];
int canReach;
position dest; //destination
int row,col;
int direction[][]={{,},{-,},{,-},{,}};
bool visited[][]; void DFS(position p){
if(p.x == dest.x && p.y == dest.y){
canReach = ;
return ;
}
for(int i=;i<;i++){
int x = p.x + direction[i][];
int y = p.y + direction[i][];
//check next direction whether match the destination position or not
if(x == dest.x && y == dest.y){
canReach = ;
return ;
}
//satisfy the searching condition
if((x <=row && x > )&&( y <= col && y>) && visited[x][y] == false && maze[x][y] ==){
position p1 = position(x,y);
visited[x][y] = true;
DFS(p1);
}
}
}
int main(){
int nCase;
cin >> nCase;
while(nCase--){
int beg_x,beg_y,end_x,end_y;
cin >> row >> col;
//initialization
canReach = ;
memset(maze,-,sizeof(maze));
memset(visited,false,sizeof(visited));
for(int i=;i<=row;i++)
for(int j=;j<=col;j++){
cin >> maze[i][j];
}
cin >> beg_x >> beg_y;
cin >> end_x >> end_y;
position p = position(beg_x,beg_y);
dest = position(end_x,end_y);
visited[beg_x][beg_y] = true;
//depth-first search
DFS(p); if(canReach){
cout<<<<endl;
}else{
cout<<<<endl;
}
}
}
上一篇:Sicily 1151 魔板


下一篇:sicily 1004. 简单哈希