#include<stdio.h> #define N (5) #include<stack> using namespace std; bool mark[N][N]; typedef struct Pos{ //位置结构体 int i, j; void set(int i, int j) { this->i = i; this->j = j; } }POS; bool IsPos(const int maze[][N], int i, int j) {//判断迷宫位置是否合法及是否已经走过 if (i >= 0 && i < N && j >= 0 && j < N &&maze[i][j] == 0 &&mark[i][j] == true) return true; else return false; } bool enable(const int maze[][N]) {//判断迷宫能否从左上角走到右下角 if(maze[0][0] == 1 || maze[N-1][N-1] == 1) return false;//左上角和右下角为1则迷宫一定不可通 stack<POS> S; for(int i=0;i<N;++i)//初始标记数组 { for(int j=0;j<N;++j) mark[i][j] = true; } mark[0][0] = false;//设置左上角已经走过 POS ps; ps.set(0, 0); S.push(ps); int pos[4][2] = { -1, 0, 0, 1, 1, 0, 0, -1 }; while (!S.empty()) { ps = S.top(); bool is = false; for (int k = 0; k < 4; ++k) { if (IsPos(maze, ps.i + pos[k][0], ps.j + pos[k][1]))//依次判断迷宫4个方向的走位 { ps.i += pos[k][0]; ps.j += pos[k][1]; if(ps.i == N-1 && ps.j ==N-1)//如果已经走到右下角，返回true return true; mark[ps.i][ps.j] = false; S.push(ps); is = true; break; } } if (!is) { S.pop(); } } return false;//没有走通，返回false } void show(int maze[][N]) {//打印迷宫方便调试 for(int i=0;i<N;++i) { for(int j=0;j<N;++j) printf("%d ", maze[i][j]); putchar('\n'); } } void exchange(int maze[][N], int n) {//将n转换成数组保存的迷宫，0为路，1为墙 for(int i=N-1;i>=0;--i) { for(int j=N-1;j>=0;--j) { maze[i][j] = n&1; n>>=1; } } /*取余法将n转换为数组保存的迷宫 stack<int> S; while(n) { S.push(n % 2); n /= 2; } while(S.size()< N*N) S.push(0); int cnt=0; int i,j; i=j=0; while(!S.empty()) { maze[i][j] = S.top(); j++; ++cnt; if(cnt == N) { j=0;++i; cnt = 0; } S.pop(); } */ } bool IsPos2(const int maze[][N], int i, int j) {//判断位置i、j迷宫是否可通 if (i >= 0 && i < N && j >= 0 && j < N &&maze[i][j] == 0)//判断该位置是否可通 return true; else return false; } bool search( int maze[][N]) { //判断按右手法则搜索A、B能否相遇，相遇返回true否则返回false int pos[4][2] = { 0, 1, -1, 0, 0, -1, 1, 0 }; POS ps1,ps2; ps1.set(0,0);//初始化A位置 ps2.set(N-1,N-1);//初始化B位置 int d1,d2;//d1、d2表示方向，0表示向右，1向上，2向左，3向下 d1=3;d2=1;//初始化方向，其中d1为A的方向，d2为B的方向，初始时A向下，B向上 while(1) { do{ if(IsPos2(maze, ps1.i+pos[d1][0],ps1.j+pos[d1][1]))//按当前方向A是否可以走到下一个位置 { ps1.i+=pos[d1][0];ps1.j+=pos[d1][1];//按当前方向A可以走到下一个位置，更新位置 d1 = (d1-1+4)%4;//更新方向为当前方向的右手边方向 break;//A走了一步，跳出循环 } else//按当前方向A不可以走到下一个位置（有墙或者出了迷宫） d1 = (d1+1+4)%4;//按逆时针更新方向 }while(1); do{//同理对B进行上述操作 if(IsPos2(maze, ps2.i+pos[d2][0],ps2.j+pos[d2][1])) { ps2.i+=pos[d2][0];ps2.j+=pos[d2][1]; d2 = (d2-1+4)%4; break; } else d2 = (d2+1+4)%4; }while(1); if(ps1.i == ps2.i && ps1.j == ps2.j)//A、B相遇，返回1 return 1; if((ps1.i == N -1 && ps1.j ==N-1) || (ps2.i == 0 && ps2.j==0) )//A、B有一个先到达终点，不可能相遇，返回0 return 0; } } int count() {//计数函数，返回A、B相遇的迷宫模式数量 int maze[N][N]; int mazeI; int cnt = 0; for(mazeI=0; mazeI< (1<<N*N); ++mazeI)//对所有可能的迷宫进行检验（总共2^(N*N)个迷宫） { exchange(maze, mazeI); if(enable(maze)) { if(search(maze)) ++cnt; } } return cnt; } int main() { printf("当n=%d时，一共有%d种满足条件的迷宫。\n",N,count()); }
时间复杂度 一般是看for循环有没有嵌套..执行了几次..
如果执行次数 是n的话 就是O(n) 如果执行次数是个常数的话,那么就是O(1)