poj1676总结

What time is it?

Description

An accutron shows time with four digits, from 0000 to 2359. Every digit is represented by 3*3 characters, including ‘|’s, ‘_’s and blanks. When the LCD screen works well, the digits look like the following:

 _     _  _     _  _  _  _  _ 

| |  | _| _||_||_ |_   ||_||_|

|_|  ||_  _|  | _||_|  ||_| _|

There are two accutrons at hand. One shows the accurate time, and the other is 15 minutes late. For example, at 8:25am, the first accutron shows ‘0825’, while the second shows ‘0810’.

Unfortunately, there is something wrong with the two LCD screens, namely some parts of the digits missed. Your task is to decide the accurate time, according to the fragmental digits showed on the two accutrons.

Input

The first line of the input is a single integer t (1 <= t <= 20), the number of test cases. Each case contains three lines, indicating the time on the accurate accutron and the time on the slow accutron, separated by a blank column. (Please refer to the Sample Input.)

Output

For each input, print the accurate time with four digits if it can be ensured, or otherwise the string ‘Not Sure’.

Sample Input

2
    _  _  _      _     _ 
  | _  _||       _   ||  
  | _ |_   |   | _    |_|
    _  _  _   _  _     _ 
  ||_  _||       _|  ||  
  | _ |_   |   ||     |_|

Sample Output

Not Sure
0825

代码

//#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
int first[4][9]={0};//first[i]为准确时间的第i位数字存储
int second[4][9]={0};//second[i]为延迟时间的第i位数字存储
int standard[10][9]={{0,1,0,1,0,1,1,1,1},
		        {0,0,0,0,0,1,0,0,1},
			{0,1,0,0,1,1,1,1,0},
			{0,1,0,0,1,1,0,1,1},
			{0,0,0,1,1,1,0,0,1},
			{0,1,0,1,1,0,0,1,1},
			{0,1,0,1,1,0,1,1,1},
			{0,1,0,0,0,1,0,0,1},
			{0,1,0,1,1,1,1,1,1},
			{0,1,0,1,1,1,0,1,1}};
int judge(int array[][9],int k,int s)
{
	int res=2;//res为0时不匹配，为1时属于，为2时等于 
	for (int i=0;i<9;i++)
	{
		if (standard[s][i]<array[k][i])
		{
			res=0;
			break;
		}
		else if (standard[s][i]>array[k][i])
		{
			res=1;
		}
	}
	return res;
}

int main()
{
	int n;
	char c;
	scanf("%d",&n);
	c=getchar();
	while (n--)
	{
		for (int i=0;i<4;i++)
		{
			for (int j=0;j<9;j++)
			{
				first[i][j]=0;
				second[i][j]=0;
			}
		}
		for (int i=0;i<3;i++)
		{
			for (int j=0;j<26;j++)
			{
				scanf("%c",&c);
				if (c=='|'||c=='_')
                                //将字符以数字的形式记录到数组中
				{
					if (j<12)
					{
						first[j/3][j%3+i*3]=1;
					}
					else
					{
						second[(j-13)/3][(j-13)%3+i*3]=1;
					}
				}
			}
		}
		int ans, anscnt = 0;
        for(int i = 0; i <= 2359; i++)
        {
			int m = i % 100;
            int h = i / 100;
            if (!judge(first,0,h/10)) continue;
            if (!judge(first,1,h%10)) continue;
            if (!judge(first,2,m/10)) continue;
            if (!judge(first,3,m%10)) continue;
            if(h >= 24 || m >= 60) continue;
            //计算延迟时间
            if ((m-15)<0)
            {
            	h=(h-1+24)%24;
			}
			m=(m-15+60)%60;
            if (!judge(second,0,h/10)) continue;
            if (!judge(second,1,h%10)) continue;
            if (!judge(second,2,m/10)) continue;
            if (!judge(second,3,m%10)) continue;
            if(h >= 24 || m >= 60) continue;
			anscnt++;
            if(anscnt == 2) break;
            ans = i;
        }
        if(anscnt != 1) puts("Not Sure");
        else printf("%04d\n", ans);
	}
	return 0;
}

反思

写这道题时，实现寻找所有可能的匹配数字很容易，之后的思路就没有那么清晰了。我尝试通过所有的可能的数字来构成精确的时间和延迟的时间，发现需要循环层数多，不直观，且构成的时间也不一定是合法的时间（例如可能会构成3825这种），为了实现这个思路写了很多函数，浪费了很多时间。

实际上只要遍历所有合法时间，来判断这个时间能不能匹配到精确时间和延迟的时间，一共也只需要进行约2400次循环，每一个循环内如果时间的某一位不匹配就可以直接continue。对于循环中每一个时间，如果每一位都匹配准确时间的数字，就可以减去15分钟算出延迟时间，再依同样的方法判断得到的时间是否与其数字匹配。