2011-09-24 20:22:38Morris
d270. 11581 - Grid Successors
d270. 11581 - Grid Successors
/**********************************************************************************/
/* Problem: d270 "11581 - Grid Successors" from UVA11581 */
/* Language: C (1092 Bytes) */
/* Result: AC(0ms, 248KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-24 13:19:47 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
typedef struct {
char s[3][3];
int num;
}G;
G g[1024];
void solve() {
int i, x, y, a, b, c;
int mark[1024], D[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
memset(mark, 0, sizeof(mark));
mark[g[0].num] = 1;
for(i = 0; i < 1024; i++) {
memset(&g[i+1], 0, sizeof(G));
for(a = 0; a < 3; a++)
for(b = 0; b < 3; b++) {
for(c = 0; c < 4; c++) {
x = a + D[c][0], y = b + D[c][1];
if(x >= 0 && x < 3 && y >= 0 && y < 3)
g[i+1].s[a][b] += g[i].s[x][y];
}
g[i+1].s[a][b] &= 1;
}
for(a = 0, c = 0; a < 3; a++)
for(b = 0; b < 3; b++)
g[i+1].num |= g[i+1].s[a][b]<<c, c++;
if(mark[g[i+1].num])
break;
mark[g[i+1].num] = 1;
}
printf("%d\n", i-1);
}
int main() {
int t, i, j, k;
scanf("%d", &t);
while(t--) {
for(i = 0; i < 3; i++) {
scanf("%s", &g[0].s[i]);
for(j = 0; j < 3; j++)
g[0].s[i][j] -= '0';
}
for(i = 0, g[0].num = 0, k = 0; i < 3; i++)
for(j = 0; j < 3; j++)
g[0].num |= (g[0].s[i][j])<<k, k++;
solve();
}
return 0;
}
內容 ：
用g表示一個 3 x 3的表格，每一格只有0跟1。我們定義一個F()，F(g)使的g每一格與他的相鄰表個相加(以二進位，產生出新的3 x 3 g
我們更進一步的定義
f (0)(g) = g
f (i+1)(g) = f(f (i)(g)) i>0
最後對於一個表格 h = f (i)(g) ，使 kg(h) 可以索引在 f (i)(g) 的 i 次是多少。但是i可能到無限大。所以我們要計算i最大可以到多少。
簡單說就是找出 使用f()可以產生幾個不同於g的個數。
由於原意太過冗長所以翻一個超簡單版本
有一個函式F()
可以使 3X3表格
作運算 (每一格都是 前一個表格的上下左右加起來%2)
111 f() 001 f() 110 f () 010 f() 000
100 ----> 100 ----> 101 ---> 101 ----> 000
001 110 011 010 000
找出有幾個與第一個不同的3X3，還有不能全部都是0
輸入說明
：
第一行是幾組測資，每組測資間有一個換行隔開，
每組有三行，一行中有三個字元(只有0跟1)代表這一個表格 g 的行列 所對應的值
輸出說明
：
對於給一個測資印出最大的 kg(f (i)(g))，
如果找不到印出-1
範例輸入 ：
3 111 100 001 101 000 101 000 000 000
範例輸出 ：
3 0 -1
提示
：
出處
：
/**********************************************************************************/
/* Problem: d270 "11581 - Grid Successors" from UVA11581 */
/* Language: C (1092 Bytes) */
/* Result: AC(0ms, 248KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-24 13:19:47 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
typedef struct {
char s[3][3];
int num;
}G;
G g[1024];
void solve() {
int i, x, y, a, b, c;
int mark[1024], D[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
memset(mark, 0, sizeof(mark));
mark[g[0].num] = 1;
for(i = 0; i < 1024; i++) {
memset(&g[i+1], 0, sizeof(G));
for(a = 0; a < 3; a++)
for(b = 0; b < 3; b++) {
for(c = 0; c < 4; c++) {
x = a + D[c][0], y = b + D[c][1];
if(x >= 0 && x < 3 && y >= 0 && y < 3)
g[i+1].s[a][b] += g[i].s[x][y];
}
g[i+1].s[a][b] &= 1;
}
for(a = 0, c = 0; a < 3; a++)
for(b = 0; b < 3; b++)
g[i+1].num |= g[i+1].s[a][b]<<c, c++;
if(mark[g[i+1].num])
break;
mark[g[i+1].num] = 1;
}
printf("%d\n", i-1);
}
int main() {
int t, i, j, k;
scanf("%d", &t);
while(t--) {
for(i = 0; i < 3; i++) {
scanf("%s", &g[0].s[i]);
for(j = 0; j < 3; j++)
g[0].s[i][j] -= '0';
}
for(i = 0, g[0].num = 0, k = 0; i < 3; i++)
for(j = 0; j < 3; j++)
g[0].num |= (g[0].s[i][j])<<k, k++;
solve();
}
return 0;
}