#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct Node{
int x;
int y;
char state;
int visited;
};
vector<vector<Node> > map;
int r,c,sx,sy;
void CrtMap(){
Node n;
cin>>r>>c;
map.resize(r+1,vector<Node>(c+1));
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
cin>>map[i][j].state;
map[i][j].x=i;
map[i][j].y=j;
map[i][j].visited=0;
if(map[i][j].state=='B'){
sx=i;
sy=j;
}
}
}
int IsAchieved;
void DFS(int sx,int sy)
{
map[sx][sy].visited=1;
if(map[sx][sy].state=='H')
{
IsAchieved=1;
return;
}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int nx,ny;
for(int i=0;i<4;i++)
{
nx=map[sx][sy].x+dir[i][0];
ny=map[sx][sy].y+dir[i][1];
if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&map[nx][ny].state!='#'&&map[nx][ny].visited!=1){
DFS(nx,ny);
}
}
}
void OutMap() {
for(int i=1;i<=r;i++) {
for(int j=1;j<=c;j++)
{
cout<<map[i][j].state;
}cout<<endl;
}
}
int main()
{
CrtMap();
OutMap();
printf("sx=%d sy=%d\n",sx,sy);
DFS(sx,sy);
IsAchieved==1?printf("Yes"):printf("No");
return 0;
}
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct Node{
int x;
int y;
char state;
int visited;
};
vector<vector<Node> > map;
int r,c,sx,sy;
void CrtMap(){
Node n;
cin>>r>>c;
map.resize(r+1,vector<Node>(c+1));
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
cin>>map[i][j].state;
map[i][j].x=i;
map[i][j].y=j;
map[i][j].visited=0;
if(map[i][j].state=='B'){
sx=i;
sy=j;
}
}
}
int IsAchieved;
void BFS()
{
queue<Node> q;
Node cn;
map[sx][sy].visited=1;
q.push(map[sx][sy]);
int nx,ny,cx,cy;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
while(!q.empty())
{
cn=q.front();
q.pop();
sx=cn.x ;
sy=cn.y ;
for(int i=0;i<4;i++){
nx=map[sx][sy].x+dir[i][0];
ny=map[sx][sy].y+dir[i][1];
if(nx>=1&&nx<=r&&ny>=1&&ny<=c&&map[nx][ny].state!='#'&&map[nx][ny].visited!=1){
if(map[nx][ny].state=='H')
{
IsAchieved=1;
return;
}
map[nx][ny].visited=1;
q.push(map[nx][ny]);
}
}
}
}
void OutMap() {
for(int i=1;i<=r;i++) {
for(int j=1;j<=c;j++)
{
cout<<map[i][j].state;
}cout<<endl;
}
}
int main()
{
CrtMap();
OutMap();
printf("sx=%d sy=%d\n",sx,sy);
BFS();
IsAchieved==1?printf("Yes"):printf("No");
return 0;
}
本蒟蒻首次发分享,不足之处请大佬指正
*/
/
name:19-1-clumzyMoving-3.cpp
description:不能到达输出N,能达到输出最小步数及走过的节点;
/
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
struct MapNode{
int x;
int y;
int px;// previous x,上一个节点的横坐标
int py;
char state;
int step;
int visited;
operator < (const MapNode &mn) const{
return step > mn.step;
}
};
vector[HTML_REMOVED] > map;
int r,c,sx,sy,hx,hy;
void CrtMap(){
cin>>r>>c;
map.resize(r+1,vector[HTML_REMOVED](c+1));
for(int i = 1; i <= r; i){
for(int j = 1; j <= c; j){
cin>>map[i][j].state;
map[i][j].x = i;
map[i][j].y = j;
map[i][j].step = 32767;
if(map[i][j].state == ‘B’){//说明这个节点是原来的家,记录下这个节点的信息
sx = i;
sy = j;
map[i][j].px = -1;
map[i][j].py = -1;
map[i][j].step = 0;
}
}
}
}
void OutMap(){
for(int i = 1; i <= r; i){
for(int j = 1; j <= c; j){
cout<<map[i][j].state<<” “;
}
cout<<endl<<endl;
}
}
int isAchieve = 0;
void DFS(int cx,int cy){//体会一下和我们前面学的多叉树的遍历是不是基本一样?
map[cx][cy].visited = 1;
if(map[cx][cy].state == ‘H’){
isAchieve = 1;
hx = cx;
hy = cy;
return;
}
int nx,ny;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};//定义上下左右走座标增量
//int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//定义上右下左走座标增量
for(int i = 0; i<4; i++){
nx = cx+dir[i][0];
ny = cy+dir[i][1];
if(nx == map[cx][cy].px && nx == map[cx][cy].py){
continue;
}
if(nx >= 1 && nx <= r && ny >=1 && ny <= c && map[nx][ny].state !=’#’){
if(map[cx][cy].step + 1 < map[nx][ny].step){
map[nx][ny].px = cx;
map[nx][ny].py = cy;
map[nx][ny].step = map[cx][cy].step + 1;
DFS(nx,ny);
}
}
}
}
void OutCorrectOrder(int x,int y){
if(x == -1){
return;
}
OutCorrectOrder(map[x][y].px,map[x][y].py);
printf(“(%d,%d)”,x,y);
}
void BFS(){
queue[HTML_REMOVED] q;
MapNode cn;//current node
int nx,ny;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};//定义上下左右走座标增量
q.push(map[sx][sy]);
while(!q.empty()){
cn = q.front();
q.pop();
for(int i = 0; i<4; i++){
nx = cn.x+dir[i][0];
ny = cn.y+dir[i][1];
if(nx == cn.px && nx == cn.py){
continue;
}
if(nx >= 1 && nx <= r && ny >=1 && ny <= c && map[nx][ny].state !=’#’){
if(map[nx][ny].step != 0 && cn.step + 1 < map[nx][ny].step){
map[nx][ny].px = cn.x;
map[nx][ny].py = cn.y;
map[nx][ny].step = cn.step + 1;
if(map[nx][ny].state == ‘H’){
isAchieve = 1;
hx = nx;
hy = ny;
return;
}
q.push(map[nx][ny]);
}
}
}
}
int main(){
if(!freopen(“19-1-clumsyBearMoving-3.in”,”r”,stdin)){
cout<<”Open file error!”;
return 0;
}
CrtMap();
OutMap();
printf("(%d,%d)\n",sx,sy); //DFS(sx,sy); //isAchieve?printf("Y\n"):printf("N\n"); BFS(); if(isAchieve){ printf("Y\n"); OutCorrectOrder(hx,hy); }else{ printf("N\n"); } return 0;
}
这样可以输出最短路径