Up

 

#include <iostream>
#include <cstdio>
using namespace std;
#define SIZE 256
int mazeArray[16][16];
int Answer;
int save_data[16][16]={0};

struct Data{
int x;
int y;
int step;
};
struct Queue{
Data data[SIZE];
int front;
int rear;
};
void initQueue(Queue* q)
{
q->front=0;
q->rear=0;
}
int Enqueue(Queue* q, Data data)
{
if(q->rear==SIZE)
{
return 0;
}
q->data[q->rear++]=data;
return 1;
}
int Dequeue(Queue* q, Data* data)
{
if(q->front==q->rear)
{
return 0;
}
*data=q->data[q->front++];
}
bool Isempty(Queue* q)
{
if(q->front==q->rear==0)
return 1;
else
return 0;
}
int main(int argc, char** argv)
{
int i, j;
/*
freopen function below opens input.txt file in read only mode, and afterward,
the program will read from input.txt file instead of standard(keyboard) input.
To test your program, you may save input data in input.txt file,
and use freopen function to read from the file when using cin function.
You may remove the comment symbols(//) in the below statement and use it.
Use #include<cstdio> or #include<stdio.h> to use the function in your program.
But before submission, you must remove the freopen function or rewrite comment symbols(//).
*/
//freopen("input.txt", "r", stdin);

/*
Input into a 2D array
*/
for (i = 0; i < 16; i++)
for (j = 0; j < 16; j++)
cin >> mazeArray[j];


Queue* a=new Queue;
Data* Dequeuedata=new Data;
Data mData;
initQueue(a);

mData.x=0;
mData.y=0;
mData.step=1;
Enqueue(a,mData);
do
{
Dequeue(a,Dequeuedata);
mData.x=Dequeuedata->x;
mData.y=Dequeuedata->y;
mData.step=Dequeuedata->step;
if(Dequeuedata->x==15 && Dequeuedata->y==15)
{
Answer=Dequeuedata->step;
break;
}
if(mazeArray[Dequeuedata->x][Dequeuedata->y+1]==0 && Dequeuedata->y+1<=15 && save_data[Dequeuedata->x][Dequeuedata->y+1]==0)
{
mData.y=Dequeuedata->y+1;
mData.step++;
Enqueue(a,mData);
mData.y--;
mData.step--;
}
if(mazeArray[Dequeuedata->x][Dequeuedata->y-1]==0 && Dequeuedata->y-1>=0&&save_data[Dequeuedata->x][Dequeuedata->y-1]==0)
{
mData.y=Dequeuedata->y-1;
mData.step++;
Enqueue(a,mData);
mData.y++;
mData.step--;
}
if(mazeArray[Dequeuedata->x+1][Dequeuedata->y]==0 && Dequeuedata->x+1<=15 && save_data[Dequeuedata->x+1][Dequeuedata->y]==0)
{
mData.x=Dequeuedata->x+1;
mData.step++;
Enqueue(a,mData);
mData.x--;
mData.step--;
}
if(mazeArray[Dequeuedata->x-1][Dequeuedata->y]==0 && Dequeuedata->x-1>=0 && save_data[Dequeuedata->x-1][Dequeuedata->y]==0)
{
mData.x=Dequeuedata->x-1;
mData.step++;
Enqueue(a,mData);
mData.x++;
mData.step--;
}
save_data[Dequeuedata->x][Dequeuedata->y]=1;
}
while(Isempty(a)); ////////////////////////////////////////////////////////////////////////////////////////
/*
Implement your algorithm here.
The answer to the case will be stored in variable Answer.
*/
/////////////////////////////////////////////////////////////////////////////////////////////
// Answer = 0;
cout << Answer;

return 0; // return 0 when no error present.
}

 

#include <stdio.h>
#include <conio.h>
int V, E, S, F;
int E1[1500], E2[1500];
int Answer1, Answer2[3];
int Free[100];
int a[100][100];
int Trace[100];
int Data[100][100];
int Answer[100];

int result1[100];
int result2[100];

int find_path(int S, int F){// find path from S to F
int v;
Free = 0;
for(v=1;v<=V;v++)
if(Free[v] && a[v]){
Trace[v]=S;
find_path(v,F);
}
if(Free[F])
return 0;
else
return 1;
}

void init(){
for(int m=0;m<100;m++){
Free[m] =1;
Trace[m] =0;
}
}

void delete_vertices(int u){
for(int m=1;m<=V;m++){
a[m]=0;
a[m]=0;
a=0;
}
}

void data_recovery(int x[100][100], int data[100][100]){
for(int m=1;m<=V;m++)
for(int n=1;n<=V;n++)
x[m][n] = data[m][n];
}

void print_matrix(int a[100][100]){
for(int m=1;m<=V;m++){
printf("\n");
for(int n=1;n<=V;n++)
printf("%d ", a[m][n]);
}
}

int main(int argc, char** argv){

freopen("input.txt", "r", stdin);
setbuf(stdout, NULL);

scanf("%d %d", &V, &E);

for(int i=1;i<=E;i++){
scanf("%d %d", &E1, &E2);
}

// add your code here
// create matrix
for(int m=1;m<=V;m++){
a[E1[m]][E2[m]] =1;
a[E2[m]][E1[m]] =1;
a[m][m] =1;
}
// print matrix
print_matrix(a);

// save data
for(int m=1;m<=V;m++)
for(int n=1;n<=V;n++)
Data[m][n] = a[m][n];
printf("\n");

// Testing Sub function
int ver =1;
delete_vertices(ver);
int k=0;
for(int m=1;m<=V;m++){
init();
if(!find_path(2,m) && m!=ver){
result1[k]=m;
k++;
}
}

for(int m=0;m<k;m++)
printf("%d ",result1[m]);

// check disconected when delete 1 vertices
/*int ver=1;
int k=0;
while(ver<=V && k!=1){
delete_vertices(ver);
for(int m=1;m<=V;m++){
for(int n=1;n<=V;n++){
init();
if(!find_path(m,n)){
Answer[k]=ver;
k++;
break;
}
}
if(k==1)
break;
}
data_recovery(a,Data);
ver++;
}
printf("%d",Answer[0]);*/
}

 

9 11
1 2
1 4
1 5
2 3
2 7
3 7
4 8
5 8
6 7
6 9
8 9