UVa211 - The Domino Effect(DFS)

importjava.io.BufferedReader;
importjava.io.InputStreamReader;
importjava.io.FileReader;
importjava.io.PrintWriter;
importjava.io.OutputStreamWriter;
importjava.io.StreamTokenizer;
importjava.io.IOException;
classMain{
publicstaticfinalbooleanDEBUG=false;
publicStreamTokenizertokenizer;
publicPrintWritercout;
BufferedReadercin;
publicfinalintROW=7;
publicfinalintCOL=8;
publicfinalintSIZE=30;
publicint[][] grid=newint[ROW][COL];
publicboolean[] vis=newboolean[SIZE];
publicint[][] flag=newint[ROW][COL];
publicint[][] map=newint[ROW][ROW];
publicint[][] dir= {{0, 1}, {1, 0}};
publicintcnt;
publicvoidinit() throwsIOException    {       
if (DEBUG) {
cin=newBufferedReader(newFileReader("d:\\OJ\\uva_in.txt"));
        } else {
cin=newBufferedReader(newInputStreamReader(System.in));
        }
tokenizer=newStreamTokenizer(cin);
cout=newPrintWriter(newOutputStreamWriter(System.out)); 
intc=1;
for (inti=0; i<ROW; i++) {
for (intj=i; j<ROW; j++) {
map[i][j] =map[j][i] =c++;
            }
        }
    }
publicintnext() throwsIOException    {
tokenizer.nextToken();
if (tokenizer.ttype==StreamTokenizer.TT_NUMBER) {
return (int)tokenizer.nval;
        } elsereturn-1;
    }
publicbooleaninput() throwsIOException    {
for (inti=0; i<ROW; i++) {
for (intj=0; j<COL; j++) {
intc=next();
if (c==-1) returnfalse;
grid[i][j] =c;
            }
        }
returntrue;
    }
publicvoiddfs(intx, inty)
    {
if (y>=COL) {
x++;
y=0;
if (x>=ROW) {
cnt++;
print();
return;
            }
        }
if (flag[x][y] !=0) dfs(x, y+1);
else {
for (inti=0; i<2; i++) {
intdx=x+dir[i][0];
intdy=y+dir[i][1];
if (dx>=ROW||dy>=COL||flag[dx][dy] !=0) continue;
intc=map[grid[x][y]][grid[dx][dy]];
if (vis[c]) continue;
vis[c] =true;
flag[x][y] =flag[dx][dy] =c;
dfs(x, y+1);
vis[c] =false;
flag[x][y] =flag[dx][dy] =0;
            }
        }
    }
publicvoidprint()
    {
for (inti=0; i<ROW; i++) {
for (intj=0; j<COL; j++) {
cout.printf("%4d", flag[i][j]);
            }
cout.println();
        }
cout.println();
    }
publicvoidsolve(intcas)
    {
if (cas!=1) {
cout.println();
cout.println();
cout.println();
        }
cout.println("Layout #"+cas+":");
cout.println();
for (inti=0; i<ROW; i++) {
for (intj=0; j<COL; j++) {
cout.printf("%4d", grid[i][j]);
            }
cout.println();
        }
cnt=0;
cout.println();
cout.println("Maps resulting from layout #"+cas+" are:");
cout.println();
dfs(0, 0);
cout.println("There are "+cnt+" solution(s) for layout #"+cas+".");
cout.flush();
    }
publicstaticvoidmain(String[] args) throwsIOException    {
Mainsolver=newMain();
solver.init();
intcas=1;
while (solver.input()) {
solver.solve(cas);
cas++;
        }
    }
}