?? main.cpp
字號:
#include <iostream.h>
#include <memory.h>
#include <fstream.h>
#define MAXX 15
#define MAXY 10
#define MAXXY 24
class Sys
{
private:
int* x;
int* y;
int* xy;//逆時針x->y
int* yx;
int tx[MAXX];
int ty[MAXY];
int txy[MAXXY];//逆時針x->y 左上角為0,0
int tyx[MAXXY];//左下角為0,0
int IsPlaced[MAXX][MAXY];
bool ok;
public:
int Result[MAXX][MAXY];
Sys(int* input_x,int* input_y,int* input_xy,int* input_yx);
void backtrack(int CurrentX,int CurrentY);
};
Sys::Sys(int* input_x,int* input_y,int* input_xy,int* input_yx)
{
ok = false;
memset(tx,0,MAXX*sizeof(int));
memset(ty,0,MAXY*sizeof(int));
memset(txy,0,MAXXY*sizeof(int));
memset(tyx,0,MAXXY*sizeof(int));
x = input_x;
y = input_y;
xy = input_xy;
yx = input_yx;
for(int i=0;i<MAXX;i++)
for(int j=0;j<MAXY;j++)
IsPlaced[i][j]=-1;//-1代表沒有用,0代表沒有放,1放了
}
void Sys::backtrack(int CurrentX,int CurrentY)
{
CurrentX++;
if(CurrentX==MAXX)
{
CurrentX=0;
CurrentY++;
}
//到達底部處理
if(CurrentY==MAXY)
{
for(int i=0;i<MAXX;i++)
if(tx[i]!=x[i])
return;
for(int i=0;i<MAXY;i++)
if(ty[i]!=y[i])
return;
for(int i=0;i<MAXXY;i++)
{
if(txy[i]!=xy[i])
return;
if(tyx[i]!=yx[i])
return;
}
for(int i=0;i<MAXX;i++)
for(int j=0;j<MAXY;j++)
Result[i][j] = IsPlaced[i][j];
ok = true;
return;
}
/////////////////////////////////////////////////////
//不夠的情況
//x
if(tx[CurrentX]+MAXY-CurrentY<x[CurrentX])
return;
//y
if(ty[CurrentY]+MAXX-CurrentX<y[CurrentY])
return;
//xy
int counts = 1;
int m=CurrentX;
int n=CurrentY;
while(m>=0&&n<MAXY)
{
m--;
n++;
counts++;
}
if(txy[CurrentX+CurrentY]+counts<xy[CurrentX+CurrentY])
return;
//yx
counts = 1;
m=CurrentX;
n=CurrentY;
while(m<MAXX&&n<MAXY)
{
m++;
n++;
counts++;
}
if(tyx[CurrentX-CurrentY+MAXY-1]+counts<yx[CurrentX-CurrentY+MAXY-1])
return;
/////////////////////////////////////////////////////
//必須放情況
if(tx[CurrentX]+MAXY-CurrentY==x[CurrentX])
IsPlaced[CurrentX][CurrentY]=1;
//y
if(ty[CurrentY]+MAXX-CurrentX==y[CurrentY])
IsPlaced[CurrentX][CurrentY]=1;
//xy
counts = 1;
m=CurrentX;
n=CurrentY;
while(m>=0&&n<MAXY)
{
m--;
n++;
counts++;
}
if(txy[CurrentX+CurrentY]+counts==xy[CurrentX+CurrentY])
IsPlaced[CurrentX][CurrentY]=1;
//yx
counts = 1;
m=CurrentX;
n=CurrentY;
while(m<MAXX&&n<MAXY)
{
m++;
n++;
counts++;
}
if(tyx[CurrentX-CurrentY+MAXY-1]+counts==yx[CurrentX-CurrentY+MAXY-1])
IsPlaced[CurrentX][CurrentY]=1;
/////////////////////////////////////////////////////
//放滿情況
if(tx[CurrentX]==x[CurrentX])
{
IsPlaced[CurrentX][CurrentY]=0;
}
if(ty[CurrentY]==y[CurrentY])
{
IsPlaced[CurrentX][CurrentY]=0;
}
//xy
if(txy[CurrentX+CurrentY]==xy[CurrentX+CurrentY])
{
IsPlaced[CurrentX][CurrentY]=0;
}
//yx
if(tyx[CurrentX-CurrentY+MAXY-1]==yx[CurrentX-CurrentY+MAXY-1])
{
IsPlaced[CurrentX][CurrentY]=0;
}
//一定放的情況
if(IsPlaced[CurrentX][CurrentY]==1)
{
tx[CurrentX]++;
ty[CurrentY]++;
txy[CurrentX+CurrentY]++;
tyx[CurrentX-CurrentY+MAXY-1]++;
backtrack(CurrentX,CurrentY);
IsPlaced[CurrentX][CurrentY]=-1;
tx[CurrentX]--;
ty[CurrentY]--;
txy[CurrentX+CurrentY]--;
tyx[CurrentX-CurrentY+MAXY-1]--;
return;
}
//一定不放的情況
if(IsPlaced[CurrentX][CurrentY]==0)
{
backtrack(CurrentX,CurrentY);
IsPlaced[CurrentX][CurrentY]=-1;
}
else
{
//回溯有先后,先放,后不放,用一個方法剪枝
//此點是所要節點
IsPlaced[CurrentX][CurrentY]=1;
tx[CurrentX]++;
ty[CurrentY]++;
txy[CurrentX+CurrentY]++;
tyx[CurrentX-CurrentY+MAXY-1]++;
backtrack(CurrentX,CurrentY);
IsPlaced[CurrentX][CurrentY]=0;
tx[CurrentX]--;
ty[CurrentY]--;
txy[CurrentX+CurrentY]--;
tyx[CurrentX-CurrentY+MAXY-1]--;
if(ok==true)
return;
//不放,進入下一層
IsPlaced[CurrentX][CurrentY]=0;
backtrack(CurrentX,CurrentY);
IsPlaced[CurrentX][CurrentY]=-1;
if(ok==true)
return;
}
}
main()
{
ifstream f("input.txt",ios::in);
ofstream of("output.txt",ios::out);
int num[4][30];
int totalx=0;
int total;
while(!f.eof())
{
total=0;
char c=0;
for(int i=0;(int)c!=10&&!f.eof();i++)
{
f>>num[totalx][total];
f.read(&c,1);
total++;
}
totalx++;
}
Sys s(num[0],num[1],num[2],num[3]);
s.backtrack(-1,0);
for(int i=0;i<MAXY;i++)
{
for(int j=0;j<MAXX;j++)
{
if(s.Result[j][i]==1)
of<<"*";
else
of<<' ';
}
of<<endl;
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -