C++ジョブコード合集
3679 ワード
子犬が迷宮を歩く:
キューのカプセル化:
#include<iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;
#define N 20
typedef struct node
{
int x,y,pre;
} node;
bool check(bool maze[][N],const int x,const int y)
{
if(x>-1&&x<N&&y>-1&&y<N&&!maze[x][y])
return true;
return false;
}
void printPath(node path[],size_t index)
{
if(path[index].pre)
printPath(path,path[index].pre);
cout<<"["<<path[index].x+1<<","<<path[index].y+1<<"]";
}
void traceMaze(bool maze[][N],node path[],size_t index)
{
static const int dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
if(path[index].x==N-1&&path[index].y==N-1)
{
printPath(path,index);
cout<<endl;
exit(0);
}
for(int i=0; i<4; i++)
{
int x=path[index].x+dir[i][0];
int y=path[index].y+dir[i][1];
int pre=index;
if(check(maze,x,y))
{
path[++index].x=x;
path[index].y=y;
path[index].pre=pre;
maze[x][y]=true;
traceMaze(maze,path,index);
maze[x][y]=false;
}
}
}
int main()
{
srand(time(NULL));
bool maze[N][N]= {{0}};
node path[N*N];
int wallNum=rand()%(N);
for(int i=0; i<wallNum; i++)
{
int x=rand()%N;
int y=rand()%N;
if((x==0&&y==0)||(x==N-1&&y==N-1)||maze[x][y])
{
i--;
continue;
}
maze[x][y]=true;
}
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
cout<<maze[i][j]<<" ";
}
cout<<endl;
}
path[1].x=0,path[1].y=0,path[1].pre=0;
traceMaze(maze,path,1);
}
キューのカプセル化:
#include<iostream>
using namespace std;
class queue
{
public:
queue();
queue(const queue&);
queue& operator =(const queue&);
~queue();
void push(const int&);
int front()const;
bool empty()const;
size_t size()const;
void pop();
private:
size_t head,rear,max_size,len;
int *data;
};
queue::queue():head(0),rear(0),max_size(3),len(0),data(0)
{
data=new int[max_size];
}
queue::queue(const queue& que)
{
head=que.head;
rear=que.rear;
max_size=que.max_size;
len=que.len;
data=new int[max_size];
for(size_t i=0;i<max_size;i++)
data[i]=que.data[i];
}
queue& queue::operator =(const queue& que)
{
head=que.head;
rear=que.rear;
max_size=que.max_size;
len=que.len;
delete []data;
data=new int[max_size];
for(size_t i=0;i<max_size;i++)
data[i]=que.data[i];
return *this;
}
queue::~queue()
{
delete []data;
}
void queue::push(const int& a)
{
if((rear+1)%max_size==head)
{
int *t=new int[max_size<<1];
for(size_t i=0;i<max_size;i++)
t[i]=data[i];
delete []data;
data=t;
max_size<<=1;
}
data[rear]=a;
rear=(rear+1)%max_size;
len++;
}
int queue::front()const
{
return data[head];
}
bool queue::empty()const
{
return rear==head;
}
size_t queue::size()const
{
return len;
}
void queue::pop()
{
head++,len--;
}
int main()
{
queue a,b;
for(int i=0;i<10;i++)
b.push(i);
a=b;
while(!b.empty())
{
cout<<b.front()<<endl;
b.pop();
}
while(!a.empty())
{
cout<<a.front()<<endl;
a.pop();
}
}