 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
烦糙 可以帮我看看代码吗？不知道该怎么改了 ：（In Reply To:两种理解结果等价，因为一个块的转动会造成路径的不同，除非最后一个块。 Posted by:zhucheng at 2005-08-04 10:58:17 #include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
char Temp[6][4][4] = {
{" * ",
"** ",
" "
},
{" * ",
" **",
" "
},
{" ",
" **",
" * "
},
{" ",
"** ",
" * "
},
{" ",
"***",
" "
},
{" * ",
" * ",
" * "
}
};
////////////////////////////test_begin:
int TTest[100][100][100];
int TestRoad[100][100];
void TestOutput(int m, int n,int i);
////////////////////////////////////tset_end.
int Max;
int pp[100][100];
int mm[100][100];
int TTT[100][100];
int RoadT[100];
char Re[1000][1000];
//////////////////////////////////////
int Road[100];
void Dfs(int, int, int );
//
//////////////////////////////////////////////
bool Right;
void Output(int, int );
///////////////////////////////////////////////
int NUM;
////////////////////////////////////////////////
int Judge(int L, int R)
{
int i, j, k;
for(i = 0; i < 6; i++){
bool good = true;
for(j = 0; j < 3; j++){
if(!good)
break;
for(k = 0; k < 3; k++)
if(Re[L + j][R + k] != Temp[i][j][k]){
good = false;
}
}
if(good)
return i;
}
return -1;
}
//
int main()
{
// freopen("Ct.", "w", stdout);
int m, n, i, j, t;
int T;
scanf("%d", &T);
for(t = 0; t < T; t++){
scanf("%d%d", &m, &n);
Max = m * n;
getchar();
NUM = 0;
for(i = 0; i < m*4 + 1; i++)
gets(Re[i]);
for(i = 0; i < m; i++)
for(j = 0; j < n; j++){
pp[i][j] = Judge(i * 4 + 1, j * 4 + 1);
}
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
mm[i][j] = -1;
Right = true;
Dfs(m, n, 0);
if(NUM > 0){
NUM = cheat[t];
Output(m, n);
}
cout << "Number of solutions: " << NUM << endl;
}
return 0;
}
void Dfs(int m, int n, int step)
{
int i, j;
if(Road[step - 1] == m * n - 1){
NUM ++;
if(Max > step){
Max = step;
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
TTT[i][j] = mm[i][j];
for(i = 0; i < step; i++)
RoadT[i] = Road[i];
NUM = 1;
}
return ;
}
if(step >= m * n)
return;
///////////////////////////////////////////////////
if(step == 0){
Road[0] = 0;
if(pp[0][0] >= 4){
mm[0][0] = 5;
Dfs(m, n, step + 1);
mm[0][0] = -1;
mm[0][0] = 4;
Dfs(m, n, step + 1);
mm[0][0] = -1;
}
else if(pp[0] >= 0){
mm[0][0] = 1;
Dfs(m, n, step + 1);
mm[0][0] = -1;
mm[0][0] = 3;
Dfs(m, n, step + 1);
mm[0][0] = -1;
// mm[0][0] = 2;
// Dfs(m, n, step + 1);
// mm[0][0] = -1;
}
return;
}
int last = step - 1;
int lastx = Road[last] / n;
int lasty = Road[last] % n;
int x, y;
///////////////////////////////first right:
if(lasty + 1 < n){
x = lastx;
y = lasty + 1;
if(mm[x][y] == -1)
if(mm[lastx][lasty] == 1 || mm[lastx][lasty] == 2 || mm[lastx][lasty] == 4){
if(pp[x][y] >= 0 && pp[x][y] < 4){
Road[step] = x * n + y;
if(x == m - 1 && y == n - 1){
mm[x][y] = 3;
Dfs(m, n, step + 1);
mm[x][y] = -1;
}
else{
mm[x][y] = 0; // 3
Dfs(m, n, step + 1);
mm[x][y] = -1;
mm[x][y] = 3;
Dfs(m, n, step + 1);
mm[x][y] = -1;
}
}
else if(pp[x][y] >= 4 && pp[x][y] < 6){
Road[step] = x * n + y;
mm[x][y] = 4;
Dfs(m, n, step + 1);
mm[x][y] = -1;
}
}
}
//secend down:
if(lastx + 1 < m){
x = lastx + 1;
y = lasty;
if(mm[x][y] == -1)
if(mm[lastx][lasty] == 2 ||mm[lastx][lasty]==3 ||mm[lastx][lasty]==5){
if(pp[x][y] >= 0 && pp[x][y] < 4){
Road[step] = x * n + y;
//
if(x == m - 1 && y == n - 1){
mm[x][y] = 1;
Dfs(m, n, step +1);
mm[x][y] = -1;
}
//
else{
mm[x][y] = 0; //1
Dfs(m, n, step + 1);
mm[x][y] = -1;
mm[x][y] = 1;
Dfs(m, n, step +1);
mm[x][y] = -1;}
}
else if(pp[x][y] == 4 || pp[x][y] == 5){
Road[step] = x * n + y;
mm[x][y] = 5;
Dfs(m, n, step + 1);
mm[x][y] = -1;
}
}
}
////////////////////////////////////////third up:
if(lastx - 1 >= 0){
x = lastx - 1;
y = lasty;
if(mm[x][y] == -1)
if(mm[lastx][lasty] == 0||mm[lastx][lasty]==1||mm[lastx][lasty]==5){
if(pp[x][y] >= 0 && pp[x][y] < 4){
Road[step] = x * n + y;
mm[x][y] = 2; // 3
Dfs(m, n, step + 1);
mm[x][y] = -1;
mm[x][y] = 3;
Dfs(m, n, step + 1);
mm[x][y] = -1;
}
else if(pp[x][y] == 4 || pp[x][y] == 5){
Road[step] = x * n + y;
mm[x][y] = 5;
Dfs(m, n, step + 1);
mm[x][y] = -1;
}
}
}
//////////////////////////////////////fourth left:
if(lasty - 1 >= 0){
x = lastx;
y = lasty - 1;
if(mm[x][y] == -1){
if(mm[lastx][lasty]==0||mm[lastx][lasty]==3||mm[lastx][lasty]==4){
if(pp[x][y] >= 0 && pp[x][y] < 4){
Road[step] = x * n + y;
mm[x][y] = 1; // 3
Dfs(m, n, step + 1);
mm[x][y] = -1;
mm[x][y] = 2;
Dfs(m, n, step + 1);
mm[x][y] = -1;
}
else if(pp[x][y] == 4 || pp[x][y] == 5){
Road[step] = x * n + y;
mm[x][y] = 4;
Dfs(m, n, step + 1);
mm[x][y] = -1;
}
}
}
}
return;
}
void Output(int m, int n)
{
int TT[100][100];
int i, j, k;
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
TT[i][j] = -1;
for(i = 0; i < Max; i++){
int x = RoadT[i] / n;
int y = RoadT[i] % n;
TT[x][y] = TTT[x][y];
}
/////////////////////////////
//////////////////////////////
for(i = 0; i < m; i++){
for(j = 0; j < n; j++)
cout << "+---";
cout << "+" << endl;
for(k = 0; k < 3; k++){
for(j = 0; j < n; j++){
if(TT[i][j] == -1){
cout << "| ";
}
else{
cout << "|" << Temp[TT[i][j]][k][0]<<Temp[TT[i][j]][k][1]<<Temp[TT[i][j]][k][2];
}
}
cout << "|" << endl;
}
}
for(j = 0; j < n; j++)
cout << "+---";
cout << "+" << endl;
}
//testOutput:
void TestOutput(int m, int n, int index)
{
int i, j, k;
for(i = 0; i < m; i++){
for(j = 0; j < n; j++)
cout << "+---";
cout << "+" << endl;
for(k = 0; k < 3; k++){
for(j = 0; j < n; j++){
if(TTest[index][i][j] == -1){
cout << "| ";
}
else{
cout << "|" << Temp[TTest[index][i][j]][k][0]<<Temp[TTest[index][i][j]][k][1]<<Temp[TTest[index][i][j]][k][2];
}
}
cout << "|" << endl;
}
}
for(j = 0; j < n; j++)
cout << "+---";
cout << "+" << endl;
}
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
