Domino Art Time Limit: 10000ms, Special Time Limit:25000ms, Memory Limit:65536KB Total submit users: 4, Accepted users: 2 Problem 11223 : No special judgement Problem description Lawliet is a very intelligent person, he is often seen solving puzzles or painting beautiful landscapes, in his new challenge he is trying to make some art with dominoes, he will draw a figure on a rectangular grid consisting of 1x1 squares by marking some of these squares, after that he will try to cover the marked squares with dominoes. As you probably know dominoes consist of pieces of size 2x1, for simplicity we assume that the dominoes can only be put horizontally or vertically and that you have an unlimited amount of dominoes available. The cover has to be perfect, meaning that the dominoes must cover only the marked positions and the dominoes must cover all of them, also all the dominoes must lie strictly inside the rectangular grid. Below are shown two examples of possible figures, which corresponds to the two first inputs in the sample input, the first is possible to cover with dominoes, while the second is not: Now your task is this: given a figure of marked squares on a rectangular grid, you must help Lawliet to determine if it is possible to exactly cover the figure with dominoes. Input The input consists of several test cases separated by blank lines. First line of each test case contains two positive integers R and C (1<=R,C<=60) the number of rows and columns of the rectangular grid, respectively. On the following R lines there is the actual configuration consisting of a grid of dots '.' and sharps '#'. Each character represents a square of the rectangular grid. A dot ‘.’ represents a square which is unmarked and a sharp ‘#’ represents a square marked to be part of the desired figure. A case when R=C=0 denotes the end of the input, this case should not be processed. Output For each test case output a line containing the number of the case (starting at 1) and only one of the following two messages: If it is impossible to cover the marked squares with dominoes configuration output a single word “Impossible”. If it is possible print the single word “Possible”. See examples below for more details. Sample Input 4 4 ..## .##. .### .### 4 4 #### ##.# ###. .#.# 4 16 ###.###.###.###. .#..#...#.#.#... .#..#...###.#... ###.###.#...###. 0 0 Sample Output Case 1: Possible Case 2: Impossible Case 3: Impossible简单的搜索吧！做的过程很哈！不过很幸运，一次ac自己都有点想不通!!!#include<iostream>using namespace std;char f[65][65];int m[65][65];struct node{ int i,j;}que[4000];int main(){ int n,M,i,j,cases=0,mark=0,fr,r; while(cin>>n>>M) {  cases++;   fr=r=0;  if(n==0||M==0) break;  for(i=1;i<=n;i++)   for(j=1;j<=M;j++)   {    cin>>f[i][j];    m[i][j]=0;   }  for(i=1;i<=n&&mark==0;i++)   for(j=1;j<=M&&mark==0;j++)   {    if(f[i][j]=='#')    {     if(i+1<=n&&f[i+1][j]=='#')     {      m[i][j]++;      m[i+1][j]++;     }     if(j+1<=M&&f[i][j+1]=='#')     {      m[i][j]++;      m[i][j+1]++;     }     if(m[i][j]==0)     {      printf("Case %d: Impossible\n",cases);      mark=1;     }     if(m[i][j]==1)      {      que[r].i=i;      que[r].j=j;      r++;     }    }   }  if(mark==1)   {   mark=0;   continue;  }  while(fr<r)  {   if(que[fr].i>1&&f[que[fr].i-1][que[fr].j]=='#')   {    f[que[fr].i][que[fr].j]='.';    f[que[fr].i-1][que[fr].j]='.';    if(que[fr].i-2>1&&f[que[fr].i-2][que[fr].j]=='#')    {     m[que[fr].i-2][que[fr].j]--;      if(m[que[fr].i-2][que[fr].j]==0)  break;     if(m[que[fr].i-2][que[fr].j]==1)      {      que[r].i=que[fr].i-2;      que[r].j=que[fr].j;      r++;     }    }    if(que[fr].j+1<=M&&f[que[fr].i-1][que[fr].j+1]=='#')    {     m[que[fr].i-1][que[fr].j+1]--;      if(m[que[fr].i-1][que[fr].j+1]==0) break;     if(m[que[fr].i-1][que[fr].j+1]==1)     {      que[r].i=que[fr].i-1;      que[r].j=que[fr].j+1;      r++;     }    }    if(que[fr].j-1>0&&f[que[fr].i-1][que[fr].j-1]=='#')    {     m[que[fr].i-1][que[fr].j-1]--;     if(m[que[fr].i-1][que[fr].j-1]==0) break;     if(m[que[fr].i-1][que[fr].j-1]==1)     {      que[r].i=que[fr].i-1;      que[r].j=que[fr].j-1;      r++;     }    }   }//if   else if(que[fr].i<n&&f[que[fr].i+1][que[fr].j]=='#')   {    f[que[fr].i][que[fr].j]='.';    f[que[fr].i+1][que[fr].j]='.';    if(que[fr].i+2>1&&f[que[fr].i+2][que[fr].j]=='#')    {     m[que[fr].i+2][que[fr].j]--;     if(m[que[fr].i+2][que[fr].j]==0) break;     if(m[que[fr].i+2][que[fr].j]==1)      {      que[r].i=que[fr].i+2;      que[r].j=que[fr].j;      r++;     }    }    if(que[fr].j+1<=M&&f[que[fr].i+1][que[fr].j+1]=='#')    {     m[que[fr].i+1][que[fr].j+1]--;     if(m[que[fr].i+1][que[fr].j+1]==0) break;     if(m[que[fr].i+1][que[fr].j+1]==1)     {      que[r].i=que[fr].i+1;      que[r].j=que[fr].j+1;      r++;     }    }    if(que[fr].j-1>0&&f[que[fr].i+1][que[fr].j-1]=='#')    {     m[que[fr].i+1][que[fr].j-1]--;     if(m[que[fr].i+1][que[fr].j-1]==0) break;     if(m[que[fr].i+1][que[fr].j-1]==1)     {      que[r].i=que[fr].i+1;      que[r].j=que[fr].j-1;      r++;     }    }   }//esle    else if(que[fr].j>1&&f[que[fr].i][que[fr].j-1]=='#')   {    f[que[fr].i][que[fr].j]='.';    f[que[fr].i][que[fr].j-1]='.';    if(que[fr].i-1>1&&f[que[fr].i-1][que[fr].j-1]=='#')    {     m[que[fr].i-1][que[fr].j-1]--;     if(m[que[fr].i-1][que[fr].j-1]==0) break;      if(m[que[fr].i-1][que[fr].j-1]==1)      {      que[r].i=que[fr].i-1;      que[r].j=que[fr].j-1;      r++;     }    }    if(que[fr].i+1<=n&&f[que[fr].i+1][que[fr].j-1]=='#')    {     m[que[fr].i+1][que[fr].j-1]--;     if(m[que[fr].i+1][que[fr].j-1]==0) break;     if(m[que[fr].i+1][que[fr].j-1]==1)     {      que[r].i=que[fr].i+1;      que[r].j=que[fr].j-1;      r++;     }    }    if(que[fr].j-2>0&&f[que[fr].i][que[fr].j-2]=='#')    {     m[que[fr].i][que[fr].j-2]--;     if(m[que[fr].i][que[fr].j-2]==0) break;     if(m[que[fr].i][que[fr].j-2]==1)     {      que[r].i=que[fr].i;      que[r].j=que[fr].j-2;      r++;     }    }   }//else   else if(que[fr].j<M&&f[que[fr].i][que[fr].j+1]=='#')   {    f[que[fr].i][que[fr].j]='.';    f[que[fr].i][j+1]='.';    if(que[fr].i-1>1&&f[que[fr].i-1][que[fr].j+1]=='#')    {     m[que[fr].i-1][j+1]--;     if(m[que[fr].i-1][que[fr].j+1]==0) break;      if(m[que[fr].i-1][que[fr].j+1]==1)      {      que[r].i=que[fr].i-1;      que[r].j=que[fr].j+1;      r++;     }    }    if(que[fr].i+1<=n&&f[que[fr].i+1][que[fr].j+1]=='#')    {     m[que[fr].i+1][que[fr].j+1]--;     if(m[que[fr].i+1][que[fr].j+1]==0) break;     if(m[que[fr].i+1][que[fr].j+1]==1)     {      que[r].i=que[fr].i+1;      que[r].j=que[fr].j+1;      r++;     }    }    if(que[fr].j+2<M&&f[que[fr].i][que[fr].j+2]=='#')    {     m[que[fr].i][que[fr].j+2]--;      if(m[que[fr].i][que[fr].j+2]==0) break;     if(m[que[fr].i][que[fr].j+2]==1)     {      que[r].i=que[fr].i;      que[r].j=que[fr].j+2;      r++;     }    }   }//else    fr++;  }//while  if(fr<r) printf("Case %d: Impossible\n",cases);  else  printf("Case %d: Possible\n",cases); } return 0;}      

评论