#include<iostream> #include<algorithm> #include<cstring> using namespace std; int m,n,col[110][110]; //color 1:r 2:y int F[110][110],_,__,nx,ny; //到当前位置所需最小金币数 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; bool vis[110][110],ab[110][110]; //able inline bool ck(){return nx<1||nx>m||ny<1||ny>m||vis[nx][ny];} void dfs(int x,int y,int num){ if(x==m&&y==m){ F[m][m]=num; return; } for(int i=0;i<4;i++){ nx=x+dx[i]; ny=y+dy[i]; if(ck()) continue; if((col[x][y]==col[nx][ny])&num<F[nx][ny]){ vis[nx][ny]=1; F[nx][ny]=num; dfs(nx,ny,num); vis[nx][ny]=0; } else if(ab[nx][ny]&&num+1<F[nx][ny]){ vis[nx][ny]=1; F[nx][ny]=num+1; dfs(nx,ny,num+1); vis[nx][ny]=0; } else if(!col[nx][ny]&&ab[x][y]&&num+2<F[nx][ny]){ F[nx][ny]=num+2; vis[nx][ny]=1; col[nx][ny]=col[x][y]; dfs(nx,ny,num+2); col[nx][ny]=0; vis[nx][ny]=0; } } } int main(){ memset(F,0x3f,sizeof(F));F[1][1]=0; scanf("%d%d",&m,&n); vis[1][1]=1; for(int i=0;i<n;i++){ scanf("%d%d",&_,&__); scanf("%d",&col[_][__]); col[_][__]++; ab[_][__]=1; } for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++) cout<<col[i][j]; cout<<endl; } dfs(1,1,0); for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++) cout<<col[i][j]; cout<<endl; } if(F[m][m]>30000) puts("-1"); else printf("%d",F[m][m]); return 0; }
时间: 2023-10-15 13:02:16 浏览: 38
这是一段 C++ 代码,主要是解决一个迷宫问题。其中,迷宫的大小为 $m\times m$,每个位置上有一个颜色(红色或黄色),有些位置可以踩踏,有些位置不能踩踏。起点为 $(1,1)$,终点为 $(m,m)$。每次可以向上下左右四个方向移动,但是需要花费一定的金币。移动时,如果两个位置的颜色相同,则不需要花费金币;如果两个位置的颜色不同,则需要花费一枚金币;如果当前位置可以踩踏,但是下一个位置不能踩踏,则需要花费两枚金币。
该代码使用了深度优先搜索(DFS)算法,通过递归实现。对于每个位置 $(x,y)$,计算到该位置所需的最小金币数 $F[x][y]$,然后递归计算下一个位置的最小金币数。在递归的过程中,使用了一些判断条件,比如判断下一个位置是否越界、是否被访问过,以及根据颜色和是否可以踩踏来判断是否需要花费金币等。最终,如果 $F[m][m]$ 的值大于 $30000$,则输出 -1,否则输出 $F[m][m]$ 的值。
需要注意的是,该代码中有一些变量名比较简单,不太容易理解,比如 _ 和 __,需要仔细阅读代码才能理解其含义。
相关问题
#include<iostream> #include<cstdio> using namespace std;是什么意思
#include<iostream> #include<cstdio> using namespace std; 是C++中的预处理指令,用于引入头文件和命名空间。
1. #include<iostream> 是引入iostream头文件,其中包含了输入输出流的定义,例如cout和cin等。
2. #include<cstdio> 是引入cstdio头文件,其中包含了C语言标准输入输出函数的定义,例如printf和scanf等。
3. using namespace std; 是使用std命名空间,std是C++标准库的命名空间,其中包含了很多常用的函数和类。
这些预处理指令的作用是为了在程序中能够使用输入输出流和标准库函数,使得程序更加方便和简洁。
#include<iostream> #include<stack> #include<queue>
这是C++的头文件引用,分别包含了输入输出流、栈和队列的类。其中iostream头文件定义了输入输出流的类,stack头文件定义了栈的类,queue头文件定义了队列的类。以下是它们的简单使用示例:
1. iostream头文件的使用:
```c++
#include<iostream>
using namespace std;
int main() {
int num;
cin >> num; // 从控制台读取一个整数
cout << "You entered " << num << endl; // 输出读取到的整数
return 0;
}
```
2. stack头文件的使用:
```c++
#include<iostream>
#include<stack>
using namespace std;
int main() {
stack<int> s; // 定义一个int类型的栈
s.push(1); // 压入元素1
s.push(2); // 压入元素2
s.push(3); // 压入元素3
while (!s.empty()) { // 遍历栈中元素
cout << s.top() << " "; // 输出栈顶元素
s.pop(); // 弹出栈顶元素
}
return 0;
}
```
3. queue头文件的使用:
```c++
#include<iostream>
#include<queue>
using namespace std;
int main() {
queue<int> q; // 定义一个int类型的队列
q.push(1); // 入队1
q.push(2); // 入队2
q.push(3); // 入队3
while (!q.empty()) { // 遍历队列中元素
cout << q.front() << " "; // 输出队首元素
q.pop(); // 弹出队首元素
}
return 0;
}
```