首页 > ACM题库 > HDU-杭电 > HDU 3144-Gokigen Naname[解题报告]HOJ
2014
03-03

HDU 3144-Gokigen Naname[解题报告]HOJ

Gokigen Naname

问题描述 :

Gokigen Naname is a Japanese puzzle game played on a square grid in which numbers in circles appear at some of the intersections on the grid.

The objective is to draw diagonal lines in each cell of the grid, such that the number in each circle equals the number of lines extending from that circle. Additionally, it is forbidden for the diagonal lines to form an enclosed loop.

Speedy Escape    Speedy Escape

The first figure shows the start position of a puzzle. The second figure shows the solution to the same puzzle. A Gokigen Naname puzzle always has exactly one solution.

输入:

The first line of the input contains a single integer n (2 <= n <= 7), the number of cells along each of the sides in the square grid. Then follow n + 1 lines containing the contents of the intersections of the grid cells. Each such line will contain a string of n+1 characters, either a digit between 0 and 4, inclusive, or a period (‘.’) indicating that there is no number at this intersection (arbitrarily many lines may connect to it).

输出:

The first line of the input contains a single integer n (2 <= n <= 7), the number of cells along each of the sides in the square grid. Then follow n + 1 lines containing the contents of the intersections of the grid cells. Each such line will contain a string of n+1 characters, either a digit between 0 and 4, inclusive, or a period (‘.’) indicating that there is no number at this intersection (arbitrarily many lines may connect to it).

样例输入:

3
1.1.
...0
.3..
..2.
5
.21...
..33.0
......
..33..
0..33.
....11

样例输出:

\//
\\\
/\/
/\\//
//\\\
\\\//
\/\\/
///\\

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>

using namespace std;
char ans[10][10];
char mat[10][10];
char input[10][10];
bool vis[10][10];
int tR, tC,N;
bool isin(int r,int c){
    return r>=0&&r<=N&&c>=0&&c<=N;
}
bool dfs(int r, int c) {
  if (vis[r][c]) return false;  
  if (r==tR && c==tC) return true;
  vis[r][c]=true;
  if (isin(r+1,c+1)&& ans[r][c]=='\\') if (dfs(r+1,c+1)) return true;
  if (isin(r-1,c-1)&& ans[r-1][c-1]=='\\') if (dfs(r-1,c-1)) return true;
  if (isin(r-1,c+1)&& ans[r-1][c]=='/') if (dfs(r-1,c+1)) return true;
  if (isin(r+1,c-1)&& ans[r][c-1]=='/') if (dfs(r+1,c-1)) return true;
  return false;
}

bool have(int r, int c, int tr, int tc) {
    int i,j;
  for (i=0;i<=N;i++)
    for (j=0;j<=N;j++) vis[i][j] = false;
  tR=tr;
  tC=tc;
  return dfs(r,c);
}
bool canput(int r, int c, char s) {
  if (s=='/' &&have(r,c+1,r+1,c)) return false;
  if (s=='\\' &&have(r,c,r+1,c+1)) return false;
  return true;
}
bool legal(int r,int c){
    if (input[r][c]!='.'&&mat[r][c]!=0) return false;
    if (r==N-1){
        if (input[r+1][c]!='.'&&mat[r+1][c]!=0) return false;
        if (c==N-1){
            
            if (input[r+1][c+1]!='.'&&mat[r+1][c+1]!=0) return false;
        }
    }
    if (c==N-1) {
        if (input[r][c+1]!='.'&&mat[r][c+1]!=0) return false;
    }
    if (mat[r][c+1]<0||mat[r+1][c]<0||mat[r+1][c+1]<0) return false;
    return true;
}
bool dfs(int now){
    if (now==N*N){
        return true;
    }
    int r = now/N,c = now%N;
    ans[r][c] = '.';
    if (canput(r,c,'/')){
        ans[r][c] = '/';
        mat[r][c+1]--;
        mat[r+1][c]--;
        if (legal(r,c)&&dfs(now+1))
            return true;
        mat[r][c+1]++;
        mat[r+1][c]++;
        ans[r][c] = '.';
    }
    if (canput(r,c,'\\')){
        ans[r][c] = '\\';
        mat[r][c]--;
        mat[r+1][c+1]--;
        if (legal(r,c)&&dfs(now+1))
            return true;
        mat[r][c]++;
        mat[r+1][c+1]++;
        ans[r][c]='.';
    }
    return false;
}

        
int main(){
    int tt;
    int i,j,st,next;
    scanf("%d",&tt);
    for (int tcas = 1;tcas<=tt;tcas++){
        
        scanf("%d",&N);
        for (i=0;i<=N;i++)
            scanf("%s",&input[i]);
        for (i=0;i<=N;i++)
            for (j=0;j<=N;j++)
            if (input[i][j]=='.') mat[i][j] = 4;
            else mat[i][j]=input[i][j]-'0';
        memset(ans,0,sizeof(ans));
        dfs(0);
        for (i=0;i<N;i++)
        {
            for (j=0;j<N;j++) printf("%c",ans[i][j]);
            printf("\n");
        }
    }
    
}

  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。