// 1WA // // なんだ? // 4*4が怪しい? // use std::io::Write; use std::collections::*; type Map = BTreeMap; type Set = BTreeSet; type Deque = VecDeque; fn main() { input! { h: usize, w: usize, } assert!((h, w) != (4, 4)); for f in [solve_c, solve_t, solve_tc].iter() { let a = (*f)(h, w); if let Some(a) = a { let v = *a.iter().flatten().max().unwrap(); println!("{}", v); for a in a { use util::*; println!("{}", a.iter().join(" ")); } } else { println!("-1"); } } /* for h in 2..11 { for w in 2..11 { println!("h, w = {h} {w}"); if let Some(a) = solve_t(h, w) { for a in a.iter() { for a in a.iter() { print!("{:3}", *a); } println!(); } } else { println!("None"); } } } */ } // TC // 3*3可能 // 3*w 可能 // 4*5 可能 // 4*w(>=5) 可能 // 4*4 無理そう // 5*5 Cおけば3*4にできて、可能 // 6*6 fn solve_tc(mut h: usize, mut w: usize) -> Option>> { let trans = h > w; if trans { std::mem::swap(&mut h, &mut w); } if h <= 2 { return None; } if (h, w) == (4, 4) { let mut ans = vec![vec![0; 4]; 4]; ans[0] = vec![1, 1, 1, 1]; ans[1] = vec![2, 1, 3, 3]; ans[2] = vec![2, 2, 2, 3]; ans[3] = vec![2, 3, 3, 3]; } let mut k = 1; let mut gen = || { let r = k; k += 1; r }; let mut a = vec![vec![0; w]; h]; let mut ox = 0; while h >= 6 { let x = gen(); let y = gen(); for i in 0..w { a[h - 3][i] = x; a[h - 2][i] = y; a[h - 1][i] = x; } a[h - 2][0] = x; a[h - 1][w - 1] = y; a[h - 3][w - 1] = y; h -= 3; } if h == 5 { let c = gen(); for i in 0..w { a[0][i] = c; a[h - 1][i] = c; } for i in 0..h { a[i][w - 1] = c; } ox += 1; h -= 2; w -= 1; } if h == 3 { let x = gen(); let y = gen(); for i in 0..w { a[ox][i] = x; a[ox + 1][i] = y; a[ox + 2][i] = x; } a[ox + 1][0] = x; a[ox][w - 1] = y; a[ox + 2][w - 1] = y; } else { let x = gen(); let y = gen(); let z = gen(); for i in 1..w { a[ox][i] = x; a[ox + 1][i] = y; a[ox + 2][i] = z; a[ox + 3][i] = x; } let p = gen(); for i in 0..4 { a[ox + i][0] = x; a[ox + i][w - 1] = p; } a[ox][w - 2] = p; a[ox + 3][w - 2] = p; a[ox][w - 3] = y; a[ox + 3][w - 3] = z; } if trans { a = transpose(a); } Some(a) } // T形 // 3*? // 3*6は可能 // 引き伸ばせる // min=3, max>=6 は可能 // 4*4は可能 // 引き伸ばせる // min=4は可能 // min=5? // 5*5 できる // 引き伸ばせる // 5*w 可能 // 6*6 // 4*4に帰着可能 // 6*w 可能 fn solve_t(mut h: usize, mut w: usize) -> Option>> { let trans = h > w; if trans { std::mem::swap(&mut h, &mut w); } if h <= 2 || (h == 3 && w < 6) { return None; } let mut k = 1; let mut gen = || { let r = k; k += 1; r }; let mut ox = 0; let mut a = vec![vec![0; w]; h]; while h >= 6 { let p = gen(); let q = gen(); let r = gen(); for i in 0..w { a[ox][i] = p; a[ox + h - 1][i] = r; } for i in 1..(h - 1) { a[ox + i][w - 1] = q; if i == 2 { a[ox + i][w - 2] = q; } else if i == 1 { a[ox + i][w - 2] = p; } else { a[ox + i][w - 2] = r; } } ox += 1; h -= 2; w -= 2; } if h == 3 { if w < 6 { return None; } let p = gen(); let q = gen(); let r = gen(); let s = gen(); for i in 0..w { a[ox][i] = if i == 0 {p} else if i == w - 1 {q} else {r}; a[ox + 1][i] = if i <= 1 {p} else if i == 2 {r} else if i == 3 {s} else {q}; a[ox + 2][i] = if i == 0 {p} else if i == w - 1 {q} else {s}; } } else if h == 4 { let p = gen(); let q = gen(); let r = gen(); let s = gen(); for i in 0..w { a[ox][i] = p; a[ox + 1][i] = q; a[ox + 2][i] = r; a[ox + 3][i] = s; } for i in 0..3 { a[ox + i][0] = q; a[ox + 1 + i][w - 1] = r; } a[ox + 2][1] = s; a[ox + 1][w - 2] = p; } else { let mut k = [0; 5]; for i in 0..5 { k[i] = gen(); } for i in 0..w { for j in 0..5 { a[ox + j][i] = k[j]; } } a[ox + 1][0] = k[2]; a[ox + 1][1] = k[0]; a[ox + 3][0] = k[2]; a[ox + 3][1] = k[4]; a[ox + 2][w - 2] = k[3]; a[ox + 2][w - 1] = k[1]; a[ox][w - 1] = k[1]; } if trans { a = transpose(a); } Some(a) } // C形 // コの組み合わせで3*4 は可能 // 3*3 は無理そう // 3*5? // 無理そう // 3*6 // 可能 // 3*(4以上の偶数) は可能 // 4*4 可能 // 4*w 可能 // 5*5 可能 // 5*w 可能 fn solve_c(mut h: usize, mut w: usize) -> Option>> { let trans = h > w; if h > w { std::mem::swap(&mut h, &mut w); } if h <= 2 || (h == 3 && w % 2 == 1) { return None; } let mut k = 1; let mut gen = || { let r = k; k += 1; r }; let mut ox = 0; let mut oy = 0; let mut a = vec![vec![0; w]; h]; while h > 5 || (h == 5 && w % 2 == 1) { let k = gen(); for i in 0..w { a[ox][oy + i] = k; a[ox + h - 1][oy + i] = k; } for i in 0..h { a[ox + i][oy] = k; } ox += 1; oy += 1; h -= 2; w -= 1; } if h == 5 { let k = gen(); for i in 0..w { a[ox][oy + i] = k; } for i in 0..h { a[ox + i][oy] = k; a[ox + i][oy + w - 1] = k; } h -= 1; w -= 2; ox += 1; oy += 1; } if h == 3 { let k = gen(); let mut p = [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2)]; let b = &mut a; let mut a = vec![vec![0; w]; h]; for &(x, y) in p.iter() { a[x][y] = k; } let mut i = 1; while i + 4 < w { let d = if i % 4 == 1 {0} else {2}; let k = gen(); a[1][i] = k; a[d][i] = k; a[d][i + 1] = k; a[d][i + 2] = k; a[d][i + 3] = k; a[1][i + 3] = k; i += 2; } for p in p.iter_mut() { p.1 = w - 1 - p.1; if i % 4 == 1 { p.0 = h - 1 - p.0; } } let k = gen(); for &(x, y) in p.iter() { a[x][y] = k; } for i in 0..h { for j in 0..w { b[ox + i][oy + j] = a[i][j]; } } } else { let x = gen(); let y = gen(); for i in 0..w { a[ox][oy + i] = x; a[ox + 1][oy + i] = if i == 0 {x} else {y}; a[ox + 2][oy + i] = if i == w - 1 {y} else {x}; a[ox + 3][oy + i] = y; } } if trans { a = transpose(a); } Some(a) } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- mod util { pub trait Join { fn join(self, sep: &str) -> String; } impl Join for I where I: Iterator, T: std::fmt::Display, { fn join(self, sep: &str) -> String { let mut s = String::new(); use std::fmt::*; for (i, v) in self.enumerate() { if i > 0 { write!(&mut s, "{}", sep).ok(); } write!(&mut s, "{}", v).ok(); } s } } } // ---------- begin transpose ---------- pub fn transpose(a: Vec>) -> Vec> { if a.is_empty() { return a; } let h = a.len(); let w = a[0].len(); assert!(a.iter().all(|a| a.len() == w)); let mut ta: Vec<_> = (0..w).map(|_| Vec::with_capacity(h)).collect(); for a in a { for (ta, a) in ta.iter_mut().zip(a) { ta.push(a); } } ta } // ---------- end transpose ----------