15.03.2011, 20:31
общий
это ответ
Здравствуйте, lamed!
#include <iostream>
#include "conio.h"
#include <stdio.h>
using namespace std;
int minimym=1200;
int put;
void obrput(int it, int *a, int *tmp, int ir, int jr, int n, int m, int nap, int count);
int main()
{
int n=20,m=40,s; // Размерность матрицы и количество стен
int in=-1,jn=-1,ik=-1,jk=-1; // Начало и конец волны
int it=0;
char t;
FILE *f1;
f1 = fopen("input.txt","r");
int *a=new int[n*m]; // Основная матрица
for (int i=0;i<n*m;i++)
a[i]=0;
int *tmp=new int[n*m]; // Матрица для хранения пути
for (int i=0; i<n; i++) // Считывание информации из файла
{
for (int j=0; j<m; j++)
{
fscanf(f1, "%c",&t);
if (t=='N')
{
a[i*m+j]=1;
in=i;
jn=j;
}
else
if (t=='E')
{
ik=i;
jk=j;
}
else
if (t=='*')
{
a[i*m+j]=-1;
}
}
fscanf(f1, "\n");
}
if (in==-1 || ik==-1) // Если отсутствует начало или конец
printf("Error! Input in file Start and End point of wave\n");
else
{
bool fl=true, f=true; // Волна
int count=1;
while (fl && f) // Пока мы не достигли конца и есть куда идти волне
{
fl=false;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
{
if (i!=0) // Если можно идти вверх
if (a[(i-1)*m+j]==count && a[i*m+j]==0)
{
fl=true; // Идем туда
a[i*m+j]=(count)%4+1;
if (i==ik && j==jk)
f=false;
}
if (i!=n-1) // Если можно идти вниз
if (a[(i+1)*m+j]==count && a[i*m+j]==0)
{
fl=true; // Идем туда
a[i*m+j]=(count)%4+1;
if (i==ik && j==jk)
f=false;
}
if (j!=0) // Если можно идти влево
if (a[i*m+j-1]==count && a[i*m+j]==0)
{
fl=true; // Идем туда
a[i*m+j]=(count)%4+1;
if (i==ik && j==jk)
f=false;
}
if (j!=m-1) // Если можно идти вправо
if (a[i*m+j+1]==count && a[i*m+j]==0)
{
fl=true; // Идем туда
a[i*m+j]=(count)%4+1;
if (i==ik && j==jk)
f=false;
}
}
count=(count)%4+1; // Изменяем инднкс волны
it++; // Увеличиваем число шагов волны
for (int i=0;i<n;i++) // Печатаем текущую ситуацию
{
for (int j=0;j<m;j++)
if (a[i*m+j]==-1)
printf("%c", 176);
else
if (a[i*m+j]==0)
if (i==ik && j==jk)
printf("E");
else
printf(".");
else
printf("%d",a[i*m+j]-1);
printf("\n");
}
getch();
}
if(!f) // Поиск обратного пути
{
printf("Put est' dlina ravna %d\n",it);
a[ik*m+jk]=-2;
// Пытаемся найти путь с наименьшим числом перегибов
for (int i=0;i<4;i++) // Выбираем последовательно начальное направление
{
put=1000; // Просматриваем 1000 различных путей
obrput(it,a,tmp,ik,jk,n,m,i+1,0); // Рекурсивно перебираем пути
}
for (int i=0;i<n;i++) // Выводим путь на экран и в файл
{
for (int j=0;j<m;j++)
if (tmp[i*m+j]==-1)
{
printf("%c", 176);
}
else
if (tmp[i*m+j]==-2)
{
if ((i==in && j==jn) || (i==ik && j==jk))
{
if ((i!=0 && tmp[(i-1)*m+j]==-2) || (i!=n-1 && tmp[(i+1)*m+j]==-2))
{
printf("%c",186);
}
else
{
printf("%c",205);
}
}
else
{
if (i!=0 && tmp[(i-1)*m+j]==-2 && i!=n-1 && tmp[(i+1)*m+j]==-2)
{
printf("%c",186);
}
else
if (j!=0 && tmp[i*m+j-1]==-2 && j!=m-1 && tmp[i*m+j+1]==-2)
{
printf("%c",205);
}
else
if (j!=0 && tmp[i*m+j-1]==-2 && i!=n-1 && tmp[(i+1)*m+j]==-2)
{
printf("%c",187);
}
else
if (j!=0 && tmp[i*m+j-1]==-2 && i!=0 && tmp[(i-1)*m+j]==-2)
{
printf("%c",188);
}
else
if (j!=m-1 && tmp[i*m+j+1]==-2 && i!=n-1 && tmp[(i+1)*m+j]==-2)
{
printf("%c",201);
}
else
if (j!=m-1 && tmp[i*m+j+1]==-2 && i!=0 && tmp[(i-1)*m+j]==-2)
{
printf("%c",200);
}
}
}
else
{
printf(".");
}
printf("\n");
}
getch();
}
else
printf("Puti net");
}
fclose(f1);
return 0;
}
// Рекурсивная процедура поиска кратчайшего пути
void obrput(int it, int *a, int *tmp, int ic, int jc, int n, int m, int nap, int count)
{
if (it==0) // Если вы пришли к началу
{
if (count<minimym) // И путь с минимальным количеством перегибов
{
for (int i=0;i<n*m;i++) // Запоминаем его
tmp[i]=a[i];
minimym=count;
}
put--;
}
else
{
switch (nap) // Продолжаем двигаться по заранее выбранному напрвлению
{
case 1: // Вверх
if (ic!=0 && put)
if (a[(ic-1)*m+jc]==(it-1)%4+1)
{
ic--;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,1,count);
a[ic*m+jc]=(it-1)%4+1;
ic++;
}
break;
case 2: // Вниз
if (ic!=n-1 && put)
if (a[(ic+1)*m+jc]==(it-1)%4+1)
{
ic++;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,2,count);
a[ic*m+jc]=(it-1)%4+1;
ic--;
}
break;
case 3: // Влево
if (jc!=0 && put)
if (a[ic*m+jc-1]==(it-1)%4+1)
{
jc--;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,3,count);
a[ic*m+jc]=(it-1)%4+1;
jc++;
}
break;
case 4: // Вправо
if (jc!=m-1 && put)
if (a[ic*m+jc+1]==(it-1)%4+1)
{
jc++;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,4,count);
a[ic*m+jc]=(it-1)%4+1;
jc--;
}
break;
}
// Если нужно повернуть и лимит путей не пончился
if (ic!=0 && put) // Вверх
if (a[(ic-1)*m+jc]==(it-1)%4+1)
{
bool q=false;
if (nap!=1)
{
q=true;
count++;
}
ic--;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,1,count);
a[ic*m+jc]=(it-1)%4+1;
ic++;
if (q)
count--;
}
if (ic!=n-1 && put) // Вниз
if (a[(ic+1)*m+jc]==(it-1)%4+1)
{
bool q=false;
if (nap!=2)
{
q=true;
count++;
}
ic++;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,2,count);
a[ic*m+jc]=(it-1)%4+1;
ic--;
if (q)
count--;
}
if (jc!=0 && put) // Влево
if (a[ic*m+jc-1]==(it-1)%4+1)
{
bool q=false;
if (nap!=3)
{
q=true;
count++;
}
jc--;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,3,count);
a[ic*m+jc]=(it-1)%4+1;
jc++;
if (q)
count--;
}
if (jc!=m-1 && put) // Вправо
if (a[ic*m+jc+1]==(it-1)%4+1)
{
bool q=false;
if (nap!=4)
{
q=true;
count++;
}
jc++;
a[ic*m+jc]=-2;
obrput(it-1,a,tmp,ic,jc,n,m,4,count);
a[ic*m+jc]=(it-1)%4+1;
jc--;
if (q)
count--;
}
}
}
5
Спасибо за оперативность! С уважением.