 |
| ||||
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 | |||||||||
起始点状态不能为Temp[2]，结束点状态不能为Temp[0]，加一个判断就行了In Reply To:烦糙 可以帮我看看代码吗？不知道该怎么改了 ：（ Posted by:littlelotus at 2005-08-04 11:17:43 > #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
